# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
25944 | 2017-06-25T07:43:18 Z | 김현수(#1087) | Cake (CEOI14_cake) | C++11 | 433 ms | 12028 KB |
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pll; const ll N = 250005; ll n, s, q, a[N], sz, li[15]; bool in[N]; struct segtree { ll val[4*N], lim; void init () { for(lim=1;lim<=N;lim<<=1); for(ll i=1;i<=n;i++) val[lim+i] = a[i]; for(ll i=lim;--i;) val[i] = max(val[2*i], val[2*i+1]); } void upd (ll P, ll V) { P += lim; while(P) {val[P] = max(val[P], V); P >>= 1;} } ll get (ll S, ll E) { ll R = 0; S += lim; E += lim; while(S <= E) { if(S%2==1) {R = max(R, val[S]); S++;} if(E%2==0) {R = max(R, val[E]); E--;} S>>=1; E>>=1; } return R; } ll lb (ll P, ll X) { P += lim; while(P&(P+1)) { if(val[P] >= X) break; P = (P-1)/2; } if(!(P&(P+1))) return 0; while(P < lim) { if(val[2*P+1] >= X) P = 2*P+1; else P = 2*P; } return P - lim; } ll rb (ll P, ll X) { P += lim; while(P&(P-1)) { if(val[P] >= X) break; P = (P+1)/2; } if(!(P&(P-1))) return n+1; while(P < lim) { if(val[2*P] >= X) P = 2*P; else P = 2*P+1; } return P - lim; } } seg; int main() { scanf("%lld%lld",&n,&s); sz = min(10ll, n); for(ll i=1;i<=n;i++) { scanf("%lld",&a[i]); if(a[i] > n-sz) { li[n-a[i]+1] = i; in[i] = true; } } seg.init(); scanf("%lld",&q); while(q--) { char typ[2]; scanf("%s",typ); if(typ[0] == 'F') { ll P, V; scanf("%lld",&P); if(P == s) puts("0"); else if(P < s) { V = seg.get(P, s-1); printf("%lld\n", seg.rb(s+1, V)-P-1); } else if(P > s) { V = seg.get(s+1, P); printf("%lld\n", P-seg.lb(s-1, V)-1); } } else { ll P, Q; scanf("%lld%lld",&P,&Q); for(ll i=1;i<Q;i++) { a[li[i]]++; seg.upd(li[i], a[li[i]]); } a[P] = a[li[Q]]+1; seg.upd(P, a[P]); li[sz+1] = (in[P] ? 0 : P); for(ll i=sz;i;i--) { if(a[li[i]] < a[li[i+1]]) { swap(li[i], li[i+1]); } } in[li[sz+1]] = false; in[P] = true; } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 12028 KB | Output is correct |
2 | Correct | 0 ms | 12028 KB | Output is correct |
3 | Correct | 0 ms | 12028 KB | Output is correct |
4 | Correct | 0 ms | 12028 KB | Output is correct |
5 | Correct | 6 ms | 12028 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 243 ms | 12028 KB | Output is correct |
2 | Correct | 159 ms | 12028 KB | Output is correct |
3 | Correct | 223 ms | 12028 KB | Output is correct |
4 | Correct | 166 ms | 12028 KB | Output is correct |
5 | Correct | 196 ms | 12028 KB | Output is correct |
6 | Correct | 213 ms | 12028 KB | Output is correct |
7 | Correct | 189 ms | 12028 KB | Output is correct |
8 | Correct | 193 ms | 12028 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 69 ms | 12028 KB | Output is correct |
2 | Correct | 63 ms | 12028 KB | Output is correct |
3 | Correct | 66 ms | 12028 KB | Output is correct |
4 | Correct | 0 ms | 12028 KB | Output is correct |
5 | Correct | 99 ms | 12028 KB | Output is correct |
6 | Correct | 116 ms | 12028 KB | Output is correct |
7 | Correct | 66 ms | 12028 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 12028 KB | Output is correct |
2 | Correct | 26 ms | 12028 KB | Output is correct |
3 | Correct | 49 ms | 12028 KB | Output is correct |
4 | Correct | 59 ms | 12028 KB | Output is correct |
5 | Correct | 76 ms | 12028 KB | Output is correct |
6 | Correct | 93 ms | 12028 KB | Output is correct |
7 | Correct | 106 ms | 12028 KB | Output is correct |
8 | Correct | 116 ms | 12028 KB | Output is correct |
9 | Correct | 369 ms | 12028 KB | Output is correct |
10 | Correct | 263 ms | 12028 KB | Output is correct |
11 | Correct | 316 ms | 12028 KB | Output is correct |
12 | Correct | 433 ms | 12028 KB | Output is correct |
13 | Correct | 389 ms | 12028 KB | Output is correct |