| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 70934 | 2018-08-23T19:32:00 Z | spencercompton | Cake (CEOI14_cake) | C++17 | 2000 ms | 83408 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;
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){
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]<=loc){
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]<=loc){
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 | 4 ms | 376 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 385 ms | 4900 KB | Output isn't correct |
| 2 | Execution timed out | 2073 ms | 8308 KB | Time limit exceeded |
| 3 | Incorrect | 513 ms | 12564 KB | Output isn't correct |
| 4 | Correct | 419 ms | 17088 KB | Output is correct |
| 5 | Incorrect | 446 ms | 21816 KB | Output isn't correct |
| 6 | Execution timed out | 2069 ms | 23608 KB | Time limit exceeded |
| 7 | Incorrect | 489 ms | 28160 KB | Output isn't correct |
| 8 | Correct | 389 ms | 33176 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 231 ms | 35384 KB | Output isn't correct |
| 2 | Incorrect | 218 ms | 36720 KB | Output isn't correct |
| 3 | Incorrect | 207 ms | 38056 KB | Output isn't correct |
| 4 | Correct | 2 ms | 38056 KB | Output is correct |
| 5 | Incorrect | 224 ms | 41360 KB | Output isn't correct |
| 6 | Incorrect | 264 ms | 43860 KB | Output isn't correct |
| 7 | Correct | 264 ms | 46028 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 79 ms | 46028 KB | Output isn't correct |
| 2 | Incorrect | 78 ms | 46028 KB | Output isn't correct |
| 3 | Incorrect | 161 ms | 46792 KB | Output isn't correct |
| 4 | Incorrect | 131 ms | 47552 KB | Output isn't correct |
| 5 | Incorrect | 213 ms | 48724 KB | Output isn't correct |
| 6 | Incorrect | 259 ms | 50576 KB | Output isn't correct |
| 7 | Incorrect | 299 ms | 52048 KB | Output isn't correct |
| 8 | Incorrect | 210 ms | 54524 KB | Output isn't correct |
| 9 | Incorrect | 825 ms | 63160 KB | Output isn't correct |
| 10 | Incorrect | 685 ms | 65292 KB | Output isn't correct |
| 11 | Incorrect | 738 ms | 69720 KB | Output isn't correct |
| 12 | Incorrect | 783 ms | 76872 KB | Output isn't correct |
| 13 | Incorrect | 869 ms | 83408 KB | Output isn't correct |