# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
70945 | 2018-08-23T19:55:19 Z | spencercompton | Cake (CEOI14_cake) | C++17 | 711 ms | 10780 KB |
#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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 376 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 367 ms | 2672 KB | Output isn't correct |
2 | Correct | 326 ms | 4056 KB | Output is correct |
3 | Incorrect | 370 ms | 4224 KB | Output isn't correct |
4 | Correct | 317 ms | 4224 KB | Output is correct |
5 | Incorrect | 416 ms | 4328 KB | Output isn't correct |
6 | Incorrect | 353 ms | 8064 KB | Output isn't correct |
7 | Incorrect | 352 ms | 8064 KB | Output isn't correct |
8 | Correct | 310 ms | 8064 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 182 ms | 8872 KB | Output isn't correct |
2 | Incorrect | 194 ms | 8904 KB | Output isn't correct |
3 | Incorrect | 205 ms | 8904 KB | Output isn't correct |
4 | Correct | 3 ms | 8904 KB | Output is correct |
5 | Incorrect | 218 ms | 9784 KB | Output isn't correct |
6 | Incorrect | 238 ms | 9784 KB | Output isn't correct |
7 | Correct | 224 ms | 9784 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 62 ms | 9784 KB | Output isn't correct |
2 | Incorrect | 61 ms | 9784 KB | Output isn't correct |
3 | Incorrect | 101 ms | 9784 KB | Output isn't correct |
4 | Incorrect | 107 ms | 9784 KB | Output isn't correct |
5 | Incorrect | 178 ms | 9784 KB | Output isn't correct |
6 | Incorrect | 206 ms | 9784 KB | Output isn't correct |
7 | Incorrect | 240 ms | 9784 KB | Output isn't correct |
8 | Incorrect | 182 ms | 9784 KB | Output isn't correct |
9 | Incorrect | 711 ms | 10736 KB | Output isn't correct |
10 | Incorrect | 610 ms | 10736 KB | Output isn't correct |
11 | Incorrect | 653 ms | 10736 KB | Output isn't correct |
12 | Incorrect | 681 ms | 10736 KB | Output isn't correct |
13 | Incorrect | 653 ms | 10780 KB | Output isn't correct |