Submission #965422

#TimeUsernameProblemLanguageResultExecution timeMemory
965422efedmrlrAbracadabra (CEOI22_abracadabra)C++17
100 / 100
647 ms57028 KiB
// #pragma GCC optimize("O3,Ofast,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> using namespace std; #define lli long long int #define MP make_pair #define pb push_back #define REP(i,n) for(int i = 0; (i) < (n); (i)++) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() void fastio() { ios_base::sync_with_stdio(false); cin.tie(NULL); } const double EPS = 0.00001; const int INF = 1e9+500; const int N = 3e5+5; const int ALPH = 26; const int LGN = 25; constexpr int MOD = 1e9+7; int n,m,q; struct SegT { vector<int> data; int sz; void reset(int s) { sz = s; data.assign(4*(sz + 3), 0); } void update(int tl, int tr, int v, int ind, int val) { if(tl == tr) { data[v] += val; return; } int tm = (tl + tr) >> 1; if(ind <= tm) { update(tl, tm, v << 1, ind, val); } else { update(tm + 1, tr, v << 1 ^ 1, ind, val); } data[v] = data[v << 1] + data[v << 1 ^ 1]; } void update(int ind, int val) { update(0, sz, 1, ind, val); } int query(int tl, int tr, int v, int val) { if(tl == tr) { return tl; } int tm = (tl + tr) >> 1; if(val <= data[v << 1]) { return query(tl, tm, v << 1, val); } else { return query(tm + 1, tr, v << 1 ^ 1, val - data[v << 1]); } } int query(int val) { return query(0, sz, 1, val); } int query2(int tl, int tr, int v, int l, int r) { if(tl >= l && tr <= r) { return data[v]; } if(tl > r || tr < l) { return 0; } int tm = (tl + tr) >> 1; return query2(tl, tm, v << 1, l, r) + query2(tm + 1, tr, v << 1 ^ 1, l, r); } int query2(int l, int r) { return query2(0, sz, 1, l, r); } }; vector<int> a, nxt; vector<array<int,3> > comp; set<array<int,3> > st; vector<int> fin; vector<array<int,3> > qu; vector<int> res; int tot = 0; void calcn() { a[n + 1] = INF; vector<array<int,2> > tmp; for(int i = 1; i<=n + 1; i++) { while(tmp.size() && tmp.back()[0] < a[i]) { nxt[tmp.back()[1]] = i; tmp.pop_back(); } tmp.pb({a[i], i}); } } int itr; int t = 0; SegT dt; void get_fin(array<int,3> bl) { // cout << bl[0] << " " << bl[1] << " " << bl[2] << endl; for(int i = bl[2]; i >= bl[1]; i--) { fin[itr--] = a[i]; } } void prt() { for(auto c : st) { cout << c[0] << " " << c[1] << " " << c[2] << "\n"; } } void get_comp() { for(int l = 1; l <= n / 2;) { int r = min(n / 2, nxt[l] - 1); st.insert({a[l], l, r}); comp.pb({a[l], l, r}); tot += r - l + 1; l = nxt[l]; } for(int l = n / 2 + 1; l <= n;) { int r = nxt[l] - 1; st.insert({a[l], l, r}); comp.pb({a[l], l, r}); tot += r - l + 1; l = nxt[l]; } t++; while(1) { // prt(); // cout << "round" << t << endl; // cout << "tot:" << tot << "\n"; if(st.empty()) break; if(t == qu[q - 1][0]) break; auto last = st.end(); last--; while(tot - ((*last)[2] - (*last)[1] + 1) >= n / 2) { tot -= ((*last)[2] - (*last)[1] + 1); st.erase(last); last = st.end(); last--; } auto el = *last; if(tot == n / 2) break; int len = el[2] - el[1] + 1; tot -= ((*last)[2] - (*last)[1] + 1); st.erase(last); int ext = tot + len - n / 2; st.insert({el[0], el[1], el[2] - ext}); comp.pb({el[0], el[1], el[2] - ext}); tot += el[2] - ext - el[1] + 1; for(int l = el[2] - ext + 1; l <= el[2];) { int r = min(el[2], nxt[l] - 1); st.insert({a[l], l, r}); tot += r - l + 1; comp.pb({a[l], l, r}); l = nxt[l]; } t++; } // while(st.size()) { // TODO // auto x = prev(st.end()); // get_fin(*x); // st.erase(x); // } sort(all(comp)); dt.reset((int)comp.size() + 5); } int ind = 0; void go() { st.clear(); tot = 0; for(; ind < q && qu[ind][0] == 0; ind++) { res[qu[ind][2]] = a[qu[ind][1]]; } for(int l = 1; l <= n / 2;) { int r = min(n / 2, nxt[l] - 1); st.insert({a[l], l, r}); tot += r - l + 1; dt.update((int)(lower_bound(all(comp), array<int,3>({a[l], l, r})) - comp.begin()), r - l + 1); l = nxt[l]; } for(int l = n / 2 + 1; l <= n;) { int r = nxt[l] - 1; st.insert({a[l], l, r}); tot += r - l + 1; dt.update((int)(lower_bound(all(comp), array<int,3>({a[l], l, r})) - comp.begin()), r - l + 1); l = nxt[l]; } t++; while(1) { for(; ind < q && qu[ind][0] == t; ind++) { if(qu[ind][1] > itr) { res[qu[ind][2]] = fin[qu[ind][1]]; } else { // cout << "que:" << qu[ind][0] << " " << qu[ind][1] << " " << qu[ind][2] << "\n"; int cur = dt.query(qu[ind][1]); // cout << comp[cur][0] << " " << comp[cur][1] << " " << comp[cur][2] << "\n"; int len = dt.query2(0, cur); // cout << "len:" << len << "\n"; int fir = qu[ind][1] - len + comp[cur][2]; // cout << "ind:" << qu[ind][1] - fir << "\n"; res[qu[ind][2]] = a[fir]; } } // prt(); // cout << "round" << t << endl; // cout << "tot:" << tot << "\n"; if(st.empty()) break; auto last = st.end(); last--; while(tot - ((*last)[2] - (*last)[1] + 1) >= n / 2) { tot -= ((*last)[2] - (*last)[1] + 1); dt.update(lower_bound(all(comp), *last) - comp.begin(), -((*last)[2] - (*last)[1] + 1)); get_fin(*last); // TODO st.erase(last); assert(st.size() != 0); last = st.end(); last--; } auto el = *last; if(tot == n / 2) break; int len = el[2] - el[1] + 1; tot -= ((*last)[2] - (*last)[1] + 1); dt.update(lower_bound(all(comp), *last) - comp.begin(), -((*last)[2] - (*last)[1] + 1)); st.erase(last); int ext = tot + len - n / 2; st.insert({el[0], el[1], el[2] - ext}); tot += el[2] - ext - el[1] + 1; dt.update(lower_bound(all(comp), array<int,3>({el[0], el[1], el[2] - ext})) - comp.begin(), el[2] - ext - el[1] + 1); for(int l = el[2] - ext + 1; l <= el[2];) { int r = min(el[2], nxt[l] - 1); st.insert({a[l], l, r}); tot += r - l + 1; dt.update(lower_bound(all(comp), array<int,3>({a[l], l, r})) - comp.begin(), r - l + 1); l = nxt[l]; } t++; } while(st.size()) { // TODO auto x = prev(st.end()); get_fin(*x); st.erase(x); } for(; ind < q; ind++) { res[qu[ind][2]] = fin[qu[ind][1]]; } } inline void solve() { cin>>n>>q; a.resize(n + 2); nxt.resize(n + 1); fin.assign(n + 1, 0); qu.resize(q); itr = n; for(int i = 1; i<=n; i++) { cin >> a[i]; } REP(i, q) { cin >> qu[i][0] >> qu[i][1]; qu[i][2] = i; } sort(all(qu)); calcn(); get_comp(); itr = n; res.assign(q, -1); t = 0; go(); REP(i, q) cout << res[i] << "\n"; } signed main() { fastio(); int test = 1; //cin>>test; while(test--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...