Submission #1235544

#TimeUsernameProblemLanguageResultExecution timeMemory
1235544tapilyocaAbracadabra (CEOI22_abracadabra)C++20
0 / 100
1826 ms138388 KiB
/*********************************************** * auth: tapilyoca * * date: 07/07/2025 at 22:42:20 * * dots: https://github.com/tapilyoca/dotilyoca * ***********************************************/ #include <bits/stdc++.h> using namespace std; const long long MOD = 1e9+7; template<typename T> using vec = vector<T>; using ll = long long; using vll = vec<ll>; using vvll = vec<vll>; using pll = pair<ll,ll>; using str = string; #define pb push_back #define dbg(x) if(1) cerr << #x << ": " << x << endl; /***********************************************/ struct Segment { ll front, sstart, send, size; Segment() : sstart(0), send(0), front(0), size(0) {} Segment(ll s, ll e, ll f) { sstart = s; send = e; front = f; size = e-s+1; } bool operator>(const Segment&two) const { if(front == two.front) { if(sstart == two.sstart) { return send > two.send; } return sstart > two.sstart; } return front > two.front; } bool operator<(const Segment&two) const { if(front == two.front) { if(sstart == two.sstart) { return send < two.send; } return sstart<two.sstart; } return front < two.front; } bool operator==(const Segment&two) const { return front == two.front and sstart==two.sstart and send==two.send and size==two.size; } void print() { cerr << front << ": (" << sstart << ", " << send << ") "; } }; struct Segtree { ll l, r; Segtree *lt, *rt; Segment val; ll sum; void combine() { sum = lt->sum + rt->sum; } Segtree(ll left, ll right, vec<Segment>&a) { sum = 0ll; l = left; r = right; lt = rt = nullptr; if(l == r) { val = a[l]; return; } ll m = (l+r)>>1; lt = new Segtree(l,m,a); rt = new Segtree(m+1,r,a); } void activate(ll i, ll b) { if(i < l or r < i) return; if(i == l and l == r) { sum += val.size * b; return; } lt->activate(i,b); rt->activate(i,b); combine(); } ll query_sum(ll ql, ll qr) { if(qr < l or r < ql) return 0; if(ql <= l and r <= qr) return sum; return lt->query_sum(ql,qr) + rt->query_sum(ql,qr); } void preorder() { if(lt) { lt->preorder(); rt->preorder(); } else { val.print(); } } }; ll walk(ll x, Segtree* root, Segtree* st) { if(st->l == st->r) { // cerr << "Found it for " << x << " on segment "; // st->val.print(); // cerr << endl; ll lt_cover = (st->l == 0 ? 0 : root->query_sum(0,st->l - 1)); ll leftover = x - lt_cover; ll og_index = leftover + st->val.sstart; // cerr << "Left covers the first " << lt_cover << endl; return og_index; } ll lt_cover = root->query_sum(0,st->lt->r); if(lt_cover > x) { return walk(x, root, st->lt); } else { return walk(x, root, st->rt); } } struct Query { ll t, x; Query() : t(0), x(0) {} Query(ll tt, ll xx) { t = tt; x = xx; } bool operator>(const Query&two) const { return t > two.t; } bool operator<(const Query&two) const { return t < two.t; } }; vll riffle(vll &at) { vll a, b; ll n = at.size(); for(int i = 0; i < n/2; i++) { a.pb(at[i]); } for(int j = n/2; j < n; j++) { b.pb(at[j]); } vll out; ll lp = 0, rp = 0; while(lp != n/2 and rp != n/2) { if(a[lp] < b[rp]) { out.pb(a[lp]); lp++; } else { out.pb(b[rp]); rp++; } } for(int i = lp; i < n/2; i++) out.pb(a[i]); for(int i = rp; i < n/2; i++) out.pb(b[i]); return out; } inline vll segmentize(vll &a) { ll n = a.size(); stack<pll> st; vll out(n,1e18); for(int i = n-1; i >= 0; i--) { while(!st.empty() and st.top().first < a[i]) st.pop(); if(!st.empty()) out[i] = st.top().second; // cerr << i << " " << out[i] << endl; st.push({a[i],i}); } return out; } void solve() { ll n, q; cin >> n >> q; vll state(n,0); for(int i = 0; i < n; i++) { cin >> state[i]; } ll T = -1; vec<Query> queries(q); for(int i = 0; i < q; i++) { ll a, b; cin >> a >> b; b--; queries[i] = Query(a,b); T = max(T,a); } sort(queries.begin(),queries.end()); T += 2; vll stateTwo = riffle(state); vll next_seg = segmentize(stateTwo); set<Segment> curr_state; set<Segment> all_states_evers; for(ll at = 0; at != 1e18; at = next_seg[at]) { ll one = at; ll two = (next_seg[at] == 1e18 ? n-1 : next_seg[at] - 1); curr_state.insert(Segment(one,two,stateTwo[at])); all_states_evers.insert(Segment(one,two,stateTwo[at])); } ll state_size = n; for(int shuffles = 1; shuffles <= T; shuffles++) { // dbg(shuffles); while(state_size > n/2) { if(state_size - (*prev(curr_state.end())).size < n/2) break; all_states_evers.insert(*prev(curr_state.end())); state_size -= (*prev(curr_state.end())).size; curr_state.erase(prev(curr_state.end())); // cerr << "hee hee hee haw" << endl; } if(state_size == n/2) break; // get the middle seg Segment midSeg = *curr_state.rbegin(); curr_state.erase(prev(curr_state.end())); ll newSS = state_size - midSeg.size; curr_state.insert(Segment(midSeg.sstart, midSeg.sstart + (n/2 - newSS) - 1, midSeg.front)); all_states_evers.insert(Segment(midSeg.sstart, midSeg.sstart + (n/2 - newSS) - 1, midSeg.front)); // resegment it for(ll at = midSeg.sstart + (n/2 - newSS); at <= midSeg.send; at = next_seg[at]) { ll one = at; ll two = (next_seg[at] > midSeg.send ? midSeg.send : next_seg[at] - 1); curr_state.insert(Segment(one,two,stateTwo[at])); all_states_evers.insert(Segment(one,two,stateTwo[at])); } } while(!curr_state.empty()) { all_states_evers.insert(*prev(curr_state.end())); curr_state.erase(prev(curr_state.end())); } vec<Segment> all_states_ever(all_states_evers.begin(), all_states_evers.end()); map<Segment,ll> seg_to_index; for(int i = 0; i < all_states_ever.size(); i++) { seg_to_index[all_states_ever[i]] = i; } Segtree st(0,all_states_ever.size()-1,all_states_ever); // cerr << "Segtree created." << endl; for(ll at = 0; at != 1e18; at = next_seg[at]) { ll one = at; ll two = (next_seg[at] == 1e18 ? n-1 : next_seg[at] - 1); curr_state.insert({one,two,stateTwo[at]}); st.activate(seg_to_index[{one,two,stateTwo[at]}],1); // cerr << "Activated: " << stateTwo[at] << ": " << one << " " << two << endl; } // cerr << "Initialized" << endl; state_size = n; ll query_pointer = 0; while(queries[query_pointer].t < 2 and query_pointer < q) { if(queries[query_pointer].t == 0) { cout << state[queries[query_pointer].x] << endl; } else { cout << stateTwo[queries[query_pointer].x] << endl; } query_pointer++; } for(int shuffles = 1; shuffles <= T; shuffles++) { // dbg(shuffles); if(query_pointer == q) return; // dbg(shuffles); while(state_size > n/2) { if(state_size - (*prev(curr_state.end())).size < n/2) break; state_size -= (*prev(curr_state.end())).size; // st.activate(seg_to_index[*prev(curr_state.end())],-1); // cerr << "Decativating " << (*prev(curr_state.end())).front << ": " << (*prev(curr_state.end())).sstart << " " << (*prev(curr_state.end())).send << endl; curr_state.erase(prev(curr_state.end())); } if(state_size == n/2) break; // get the middle seg Segment midSeg = *curr_state.rbegin(); st.activate(seg_to_index[*prev(curr_state.end())],-1); // cerr << "Decativating " << (*prev(curr_state.end())).front << ": " << (*prev(curr_state.end())).sstart << " " << (*prev(curr_state.end())).send << endl; curr_state.erase(prev(curr_state.end())); ll newSS = state_size - midSeg.size; curr_state.insert({midSeg.sstart, midSeg.sstart + (n/2 - newSS) - 1, midSeg.front}); st.activate(seg_to_index[{midSeg.sstart, midSeg.sstart + (n/2 - newSS) - 1, midSeg.front}],1); // resegment it for(ll at = midSeg.sstart + (n/2 - newSS); at <= midSeg.send; at = next_seg[at]) { ll one = at; ll two = (next_seg[at] > midSeg.send ? midSeg.send : next_seg[at] - 1); curr_state.insert({one,two,stateTwo[at]}); st.activate(seg_to_index[{one,two,stateTwo[at]}],1); // cerr << "Activate "; // Segment(one,two,stateTwo[at]).print(); // cerr << endl; } // done. now check if this is a query while(query_pointer < q and shuffles + 1 == queries[query_pointer].t) { // cerr << "We are doing things!" << endl; ll ogdex = walk(queries[query_pointer].x, &st, &st); cout << stateTwo[ogdex] << endl; query_pointer++; } } st.preorder(); cerr << endl; while(query_pointer < q) { ll ogdex = walk(queries[query_pointer].x, &st, &st); // dbg(ogdex) cout << stateTwo[ogdex] << endl; query_pointer++; } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); int t = 1; while(t--) { solve(); } return 0; } /* 7 5 2 8 4 3 6 1 9 10 3 6 1 7 5 2 8 4 9 10 2 3 6 1 7 5 8 4 9 10 [2] [3] [5] [6 1] [7] [8 4] [9] [10] */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...