Submission #116991

#TimeUsernameProblemLanguageResultExecution timeMemory
116991JohnTitorCake (CEOI14_cake)C++11
0 / 100
2075 ms25592 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i, j, k) for(int i=(j); i<=(k); i++) #define FFOR(i, j, k) for(int i=(j); i<(k); i++) #define DFOR(i, j, k) for(int i=(j); i>=(k); i--) #define bug(x) cerr<<#x<<" = "<<(x)<<'\n' #define pb push_back #define mp make_pair #define bit(s, i) (((s)>>(i))&1LL) #define mask(i) ((1LL<<(i))) #define builtin_popcount __builtin_popcountll #define __builtin_popcount __builtin_popcountll using ll=long long; using ld=long double; mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2; template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;} template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);} template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);} template <typename T> inline void writeln(T x){write(x); putchar('\n');} #define taskname "Cake" int n, a; int d[250001]; vector <int> highest; class segment_tree{ public: using pointer=segment_tree*; pointer left, right; int l, r, m; int b; segment_tree(int l, int r){ this->l=l; this->r=r; m=(l+r)/2; if(l==r) b=l; else{ left=new segment_tree(l, m); right=new segment_tree(m+1, r); if(d[left->b]>d[right->b]) b=left->b; else b=right->b; } } int get_max(int u, int v){ if(l>v||r<u) return 0; if(u<=l&&v>=r) return d[b]; else return max(left->get_max(u, v), right->get_max(u, v)); } int find_last_from_left(int maxd){ if(l==r) return (d[l]<=maxd)?l:(l-1); if(d[left->b]>maxd) return left->find_last_from_left(maxd); else return right->find_last_from_left(maxd); } int find_last_from_right(int maxd){ if(l==r) return (d[r]<=maxd)?r:(r+1); if(d[right->b]>maxd) return right->find_last_from_right(maxd); else return left->find_last_from_right(maxd); } void update(int u){ if(l==r) return; else{ if(m>=u) left->update(u); else right->update(u); if(d[left->b]>d[right->b]) b=left->b; else b=right->b; } } }; segment_tree::pointer tl, tr; int main(){ #ifdef Aria if(fopen(taskname".in", "r")) freopen(taskname".in", "r", stdin); #endif // Aria read(n); read(a); FOR(i, 1, n){ read(d[i]); if(d[i]>n-10) highest.pb(i); } sort(highest.begin(), highest.end(), [](int a, int b){ return d[a]>d[b]; }); if(a!=1&&a!=n){ tl=new segment_tree(1, a-1); tr=new segment_tree(a+1, n); } { int q; char c; int i, e; read(q); while(q--){ while(!isalpha(c=getchar())); if(c=='F'){ read(i); if(i==a) writeln(0); else if(a==1||a==n) writeln(abs(a-i)); else if(i>a) writeln(i-tl->find_last_from_right(tr->get_max(a+1, i))); else writeln(tr->find_last_from_left(tl->get_max(i, a-1))-i); } else{ read(i); read(e); if(a==1||a==n) continue; for(auto &x: highest) if(x==i){ swap(x, highest.back()); highest.pop_back(); break; } highest.pb(i); int last=0; FFOR(j, 0, e){ last=d[highest[j]]; d[highest[j]]++; } d[i]=last; sort(highest.begin(), highest.end(), [](int a, int b){ return d[a]>d[b]; }); if(i>a) tr->update(i); if(i<a) tl->update(i); } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...