Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
vector<int> s(4);
for (int& x : s) cin >> x;
if (min(s[0], s[1]) > max(s[2], s[3]) || max(s[0], s[1]) < min(s[2], s[3]))
cout << "NO\n";
else
cout << "YES\n";
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
sort(a.begin(), a.end(), [](int x, int y) {
return x % 2 < y % 2;
});
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
ans += __gcd(a[i], a[j] * 2) > 1;
}
}
cout << ans << endl;
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
vector<vector<int>> lst(2, vector<int>(2, -1));
long long ans = 0;
for (int i = 0; i < int(s.size()); ++i) {
int j = i - 1;
int p = i & 1;
if (s[i] != '1') j = min(j, max(lst[0][p ^ 1], lst[1][p]));
if (s[i] != '0') j = min(j, max(lst[0][p], lst[1][p ^ 1]));
ans += i - j;
if (s[i] != '?') lst[s[i] - '0'][p] = i;
}
cout << ans << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int k;
cin >> k;
string s;
cin >> s;
reverse(s.begin(), s.end());
int n = 1 << k;
vector<int> cnt(2 * n, 1);
auto upd = [&](int i) {
return cnt[i] = (s[i] != '0' ? cnt[i * 2 + 1] : 0) + (s[i] != '1' ? cnt[i * 2 + 2] : 0);
};
for (int i = n - 2; i >= 0; i--) {
upd(i);
}
int q;
cin >> q;
while (q--) {
int p;
char c;
cin >> p >> c;
p = n - p - 1;
s[p] = c;
while (p) {
upd(p);
p = (p - 1) / 2;
}
cout << upd(0) << '\n';
}
}
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
out << "[";
fore(i, 0, sz(v)) {
if(i) out << ", ";
out << v[i];
}
return out << "]";
}
const int INF = int(1e9);
const li INF64 = li(1e18);
const int LOG = 20;
int q;
vector<int> a, c;
vector<int> p[LOG];
int main() {
cin >> q;
a.resize(q + 1);
c.resize(q + 1);
fore (lg, 0, LOG)
p[lg].resize(q + 1);
fore (lg, 0, LOG)
p[lg][0] = 0;
cin >> a[0] >> c[0];
fore (id, 1, q + 1) {
int tp; cin >> tp;
if (tp == 1) {
int pr; cin >> pr;
cin >> a[id] >> c[id];
p[0][id] = pr;
fore (lg, 1, LOG)
p[lg][id] = p[lg - 1][p[lg - 1][id]];
}
else {
int v, w;
cin >> v >> w;
int ansR = 0;
li ansS = 0;
while (w > 0 && a[v] > 0) {
int u = v;
for (int lg = LOG - 1; lg >= 0; lg--) {
if (a[p[lg][u]] > 0)
u = p[lg][u];
}
int mn = min(a[u], w);
a[u] -= mn;
w -= mn;
ansR += mn;
ansS += mn * 1ll * c[u];
}
cout << ansR << " " << ansS << endl;
}
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int LN = 20;
const int K = 12000;
int pw2[1 << LN];
vector<int> sorted_segments(const string& s)
{
int n = int(s.size()) - 1;
vector<int> res(n);
for(int i = 0; i < n; i++)
if(s[i] <= s[i + 1])
res[i] = 0;
else
res[i] = 1;
return res;
}
vector<int> prefix_sum(const vector<int>& s)
{
int n = s.size();
vector<int> p(n + 1);
for(int i = 0; i < n; i++)
p[i + 1] = p[i] + s[i];
return p;
}
int naiveLCP(const string& s, const string& t)
{
int ans = 0;
int n = s.size();
int m = t.size();
while(ans < n && ans < m && s[ans] == t[ans])
ans++;
return ans;
}
vector<vector<int>> build_table(const vector<int>& a)
{
int n = a.size();
vector<vector<int>> table(LN, vector<int>(n));
for(int i = 0; i < n; i++)
table[0][i] = a[i];
for(int i = 1; i < LN; i++)
for(int j = 0; j < n; j++)
if(j + (1 << (i - 1)) < n)
table[i][j] = min(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
else
table[i][j] = table[i - 1][j];
return table;
}
struct LCP
{
vector<int> idx;
vector<vector<int>> table;
int query_inner(int x, int y)
{
if(x > y) swap(x, y);
int len = y - x;
int d = pw2[len];
return min(table[d][x], table[d][y - (1 << d)]);
}
int query(int x, int y)
{
return query_inner(idx[x], idx[y]);
}
LCP() {};
LCP(vector<string> s)
{
int n = s.size();
vector<pair<string, int>> t;
for(int i = 0; i < n; i++)
{
t.push_back(make_pair(s[i], i));
}
sort(t.begin(), t.end());
idx.resize(n);
for(int i = 0; i < n; i++)
{
idx[t[i].second] = i;
}
vector<int> LCPs;
for(int i = 0; i < n - 1; i++)
LCPs.push_back(naiveLCP(t[i].first, t[i + 1].first));
table = build_table(LCPs);
};
};
const int T = int(2e7);
map<char, int> nxt[T];
int cur = 1;
int root = 0;
int cnt[T];
void clear_trie()
{
root = cur++;
}
int go(int x, char c)
{
if(!nxt[x].count(c))
nxt[x][c] = cur++;
return nxt[x][c];
}
void add(int v, const string& s, int l, int r, int n, bool sw, const vector<int>& ps)
{
if(sw && l + r < n - 1 && ps[n - r - 1] == ps[l])
{
cnt[v]++;
}
if(sw)
{
if(l + r < n - 1)
add(go(v, s[n - r - 1]), s, l, r + 1, n, sw, ps);
}
else
{
add(go(v, '$'), s, l, r, n, true, ps);
if(l < n - 1)
add(go(v, s[l]), s, l + 1, r, n, sw, ps);
}
}
int calc(int v, const string& s, int l, int r, int n, bool sw, const vector<vector<int>>& good)
{
int ans = 0;
if(sw && l + r < n - 1 && good[l][r])
{
ans = cnt[v];
}
if(sw)
{
if(l + r < n)
ans += calc(go(v, s[n - r - 1]), s, l, r + 1, n, sw, good);
}
else
{
ans += calc(go(v, '$'), s, l, r, n, true, good);
if(l < n)
ans += calc(go(v, s[l]), s, l + 1, r, n, sw, good);
}
return ans;
}
long long solve_short(vector<string> s, int n)
{
long long ans = 0;
clear_trie();
sort(s.begin(), s.end());
for(int i = 0; i < n; i++)
{
string cur = s[i];
int len = cur.size();
vector<vector<int>> good(len + 1, vector<int>(len + 1));
for(int l = 0; l < len; l++)
{
set<char> q;
for(int r = l; r < len; r++)
{
q.insert(cur[r]);
if(cur[l] != *q.begin() && cur[r] != *q.rbegin())
{
good[l][len - r - 1] = 1;
}
}
}
vector<int> p = prefix_sum(sorted_segments(cur));
add(root, cur, 0, 0, len, false, p);
ans += calc(root, cur, 0, 0, len, false, good);
}
ans = n * 1ll * (n - 1) - ans;
return ans;
}
long long solve_long(vector<string> s, int n)
{
int len = s[0].size();
sort(s.begin(), s.end());
vector<string> t = s;
for(int i = 0; i < n; i++)
reverse(t[i].begin(), t[i].end());
LCP ls(s);
LCP lt(t);
long long ans = 0;
for(int i = 0; i < n; i++)
{
vector<int> aux = prefix_sum(sorted_segments(s[i]));
for(int j = i + 1; j < n; j++)
{
int lf = ls.query(i, j);
int rg = lt.query(i, j);
if(aux[len - rg - 1] - aux[lf] == 0)
ans++;
else
ans += 2;
}
}
return ans;
}
long long solve_class(vector<string> s, int n)
{
if(n <= K)
return solve_long(s, n);
else
return solve_short(s, n);
}
vector<int> get_class(string s)
{
vector<int> c(26);
for(auto x : s) c[x - 'a']++;
return c;
}
int main()
{
pw2[1] = 0;
for(int i = 2; i < (1 << LN); i++)
pw2[i] = pw2[i >> 1] + 1;
int n;
cin >> n;
vector<string> s(n);
for(int i = 0; i < n; i++)
cin >> s[i];
long long ans = 0;
map<vector<int>, vector<string>> classes;
for(int i = 0; i < n; i++)
classes[get_class(s[i])].push_back(s[i]);
int cnt = 0;
for(auto x : classes)
{
ans += solve_class(x.second, x.second.size());
ans += cnt * 1337ll * x.second.size();
cnt += x.second.size();
}
cout << ans << endl;
}