Submission #445641

#TimeUsernameProblemLanguageResultExecution timeMemory
445641grtSpecijacija (COCI20_specijacija)C++17
20 / 110
4151 ms803040 KiB
#include <bits/stdc++.h> #define ST first #define ND second #define PB push_back //#define int long long using namespace std; using ll = long long; using pi = pair<int,int>; using vi = vector<int>; const int nax = 400 * 1000 + 10; int n, q, t; ll seq[nax]; struct Node { ll g; int ti, lft, rght; }; vector<Node>T1[(1 << 20)]; vector<Node>T2[nax]; vector<Node>T3[(1<<20)]; int R; vi V[nax]; map<ll,int>sc; ll starting[nax]; void add(int a, int b, int x, int ti, int l, int r, int v) { if(a <= l && r <= b) { T1[v].PB({T1[v].back().g + x, ti, (int)T1[2*v].size() - 1, (int)T1[2*v+1].size() - 1}); return; } int mid = (l + r) / 2; if(a <= mid) add(a, b, x, ti, l, mid, v*2); if(b > mid) add(a,b,x,ti,mid + 1,r,v*2+1); T3[v].PB({max(T3[2*v].back().g + T1[2*v].back().g, T3[2*v+1].back().g + T1[2*v+1].back().g), ti, (int)T3[2*v].size() - 1, (int)T3[2*v+1].size() - 1}); T1[v].PB({T1[v].back().g, ti, (int)T1[2*v].size() - 1, (int)T1[2*v+1].size() - 1}); } inline void ustaw(int a, ll x, int ti) { T2[a].PB({x, ti, -1,-1}); } inline ll askVal(int x) { return T2[x].back().g; } inline int g(vector<Node>&vec, int ti) { int low = 0, high = (int)vec.size() - 1, mid; while(low <= high) { mid = (low + high) >> 1; if(vec[mid].ti >= ti) { low = mid + 1; } else { high = mid - 1; } } return low - 1; } inline ll askVal2(int x, int ti) { int ind = g(T2[x], ti); return T2[x][ind].g; } inline int f(int x) { int v = 1; int delta = 0; while(v < R) { delta += T1[v].back().g; if(T3[2*v].back().g + T1[2*v].back().g + delta >= x) { v = v * 2; } else { v = v * 2 + 1; } } v -= R; if(v > n + 1) v = n + 2; return v; } inline int f2(int x, int ti) { int v = 1; int ind = g(T1[v], ti); int ind2 = g(T3[v], ti); int delta = 0; while(v < R) { delta += T1[v][ind].g; if(T3[2*v][T3[v][ind2].lft].g + T1[2*v][T1[v][ind].lft].g + delta >= x) { ind = T1[v][ind].lft; ind2 = T3[v][ind2].lft; v = v * 2; } else { ind = T1[v][ind].rght; ind2 = T3[v][ind2].rght; v = v * 2 + 1; } } v -= R; if(v > n + 1) v = n + 2; return v; } inline ll ustal(ll x) { int low = 1, high = n + 1, mid; while(low <= high) { mid = (low + high) >> 1; if(starting[mid] <= x) { low = mid + 1; } else { high = mid - 1; } } low--; int k = x - starting[low] + 1; int dep = low; int pos = f2(k, dep); return askVal2(pos, dep); } int par[nax][19], dp[nax]; ll inv[nax]; inline void dfs(int x) { for(int nbh : V[x]) { dp[nbh] = dp[x] + 1; dfs(nbh); par[nbh][0] = x; } } inline int lca(int a, int b) { if(dp[a] < dp[b]) swap(a, b); for(int i = 18; i >= 0; --i) { if(dp[par[a][i]] >= dp[b]) { a = par[a][i]; } } if(a == b) return -a; for(int i = 18; i >= 0; --i) { if(par[a][i] != par[b][i]) { a = par[a][i]; b = par[b][i]; } } return par[a][0]; } __int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> q >> t; ll start = 1; for(int i = 1; i <= n; ++i) { starting[i] = start; cin >> seq[i]; sc[seq[i]]; start += i; } starting[n + 1] = start; R = 1; while(R <= n + 2) R *= 2; for(int i = 1; i < 2 * R; ++i) { T1[i].PB({0, n + 2}); T3[i].PB({0, n + 2}); } //cerr << "Done0\n"; for(int i = 1; i <= n + 1; ++i) { add(i, i, i, n + 1, 0, R - 1, 1); ustaw(i, start + i - 1, n + 1); sc[start + i - 1]; } //cerr << "Done\n"; int nr = 1; for(auto &it : sc) { inv[nr] = it.ST; it.ND = nr++; } for(int i = n; i >= 1; --i) { // val = a[i] + i - start + 1 int val = seq[i] + i - start + 1; int pos = f(val + 1); int l = f(val); //cout << pos << " " << l << " " << r << "\n"; ll val1 = askVal(l); ll val2 = askVal(pos); V[sc[seq[i]]].PB(sc[val1]); V[sc[seq[i]]].PB(sc[val2]); ustaw(l, seq[i], i); add(pos, n + 1, -1, i, 0, R - 1, 1); start -= i; } ll ans = 0; dp[1] = 1; dfs(sc[1]); for(int s = 1; s <= 18; ++s) { for(int i = 1; i <= nr; ++i) { par[i][s] = par[par[i][s - 1]][s - 1]; } } while(q--) { ll x, y; cin >> x >> y; x = ((x - 1 + t * ans)%((ll)(n+1)*(n+2)/2)) + 1; y = ((y - 1 + t * ans)%((ll)(n+1)*(n+2)/2)) + 1; ll xa = ustal(x); ll ya = ustal(y); if(xa == ya) { cout << min(x, y) << "\n"; ans = min(x, y); continue; } int l = lca(sc[xa], sc[ya]); if(l < 0) { cout << min(x, y) << "\n"; ans = min(x, y); continue; } cout << inv[l] << "\n"; ans = inv[l]; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...