Submission #70945

#TimeUsernameProblemLanguageResultExecution timeMemory
70945spencercomptonCake (CEOI14_cake)C++17
0 / 100
711 ms10780 KiB
#include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); //O(N + (10 + log N)Q) //no treap bs :) int n, s; cin >> n >> s; s--; int bigs = min(n,10); bool isbig[n]; int pos[n]; int aux = 0; int top[bigs]; for(int i = 0; i<n; i++){ cin >> pos[i]; pos[i] = n-pos[i]; isbig[i] = pos[i]<bigs; if(pos[i]<bigs){ top[pos[i]] = i; } } vector<int> l; vector<int> r; for(int i = s-1; i>=0; i--){ if(l.size()==0 || pos[l.back()]>pos[i]){ l.push_back(i); } } for(int i = s+1; i<n; i++){ if(r.size()==0 || pos[r.back()]>pos[i]){ r.push_back(i); } } int q; cin >> q; for(int z = 0; z<q; z++){ string str; cin >> str; if(str=="E"){ int ind, loc; cin >> ind >> loc; ind--; loc--; vector<int> nex; aux++; for(int i = 0; i<loc; i++){ nex.push_back(top[i]); } nex.push_back(ind); for(int i = loc; i<bigs; i++){ if(top[i]==ind){ continue; } nex.push_back(top[i]); } for(int i = 0; i<bigs; i++){ isbig[nex[i]] = true; pos[nex[i]] = i; top[i] = nex[i]; } if(nex.size()>bigs){ assert(nex.size()==bigs+1); isbig[nex[bigs]] = false; pos[nex[bigs]] = -aux + bigs; } nex.clear(); if(ind<s){ vector<int> el; while(l.size()>0){ int cur = l.back(); if(isbig[cur] && pos[cur]<=pos[ind]){ el.push_back(cur); l.pop_back(); } else{ break; } } if(el.size()==0 || el.back()<ind){ el.push_back(ind); while(l.size()>0 && l.back()<=ind){ l.pop_back(); } } while(el.size()>0){ l.push_back(el.back()); el.pop_back(); } } else if(ind>s){ vector<int> er; while(r.size()>0){ int cur = r.back(); if(isbig[cur] && pos[cur]<=pos[ind]){ er.push_back(cur); r.pop_back(); } else{ break; } } if(er.size()==0 || er.back()>ind){ er.push_back(ind); while(r.size()>0 && r.back()>=ind){ r.pop_back(); } } while(er.size()>0){ r.push_back(er.back()); er.pop_back(); } } } if(str=="F"){ //get answer for this int ind; cin >> ind; ind--; int ret = 0; if(ind<s){ ret += s-ind; int lo = 0; int hi = l.size()-1; while(lo<hi){ int mid = (lo+hi+1)/2; if(l[mid]>=ind){ lo = mid; } else{ hi = mid-1; } } int bar = pos[l[lo]]; if(!isbig[l[lo]]){ bar = pos[l[lo]] + aux; } if(r.size()>0){ int val = pos[r.back()]; if(!isbig[r.back()]){ val = pos[r.back()] + aux; } if(val>=bar){ ret += n-s-1; } else{ int lo = 0; int hi = r.size()-1; while(lo<hi){ int mid = (lo+hi)/2; val = pos[r[mid]]; if(!isbig[r[mid]]){ val = pos[r[mid]] + aux; } if(val>=bar){ lo = mid+1; } else{ hi = mid; } } ret += r[lo]-s-1; } } } else if(ind>s){ ret += ind-s; int lo = 0; int hi = r.size()-1; while(lo<hi){ int mid = (lo+hi+1)/2; if(r[mid]>=ind){ lo = mid; } else{ hi = mid-1; } } int bar = pos[r[lo]]; if(!isbig[r[lo]]){ bar = pos[r[lo]] + aux; } if(l.size()>0){ int val = pos[l.back()]; if(!isbig[l.back()]){ val = pos[l.back()] + aux; } if(val>=bar){ ret += s; } else{ int lo = 0; int hi = l.size()-1; while(lo<hi){ int mid = (lo+hi)/2; val = pos[l[mid]]; if(!isbig[l[mid]]){ val = pos[l[mid]] + aux; } if(val>=bar){ lo = mid+1; } else{ hi = mid; } } ret += s-l[lo]-1; } } } cout << ret << endl; } } }

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:64:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(nex.size()>bigs){
       ~~~~~~~~~~^~~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from cake.cpp:1:
cake.cpp:65:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        assert(nex.size()==bigs+1);
               ~~~~~~~~~~^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...