# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
65926 | 2018-08-09T06:10:31 Z | ikura355 | 케이크 (CEOI14_cake) | C++14 | 659 ms | 6300 KB |
#include<bits/stdc++.h> using namespace std; const int maxn = 250000 + 5; int n,st,q; int a[maxn]; int pos[maxn]; int limit; int seg[maxn*4]; void init() { limit = 1; while(limit<=n) limit*=2; } void update(int x, int val) { x += limit; seg[x] = val; while(x) { x/=2; seg[x] = max(seg[x<<1], seg[x<<1|1]); } } int query(int l, int r) { int ans = 0; l += limit; r += limit; while(l<r) { if(l%2!=0) ans = max(ans, seg[l++]); if(r%2==0) ans = max(ans, seg[r--]); l/=2; r/=2; } if(l==r) ans = max(ans, seg[l]); return ans; } int main() { scanf("%d%d",&n,&st); for(int i=1;i<=n;i++) scanf("%d",&a[i]); init(); for(int i=1;i<=n;i++) { pos[n-a[i]+1] = i; update(i,a[i]); } scanf("%d",&q); while(q--) { char type; scanf(" %c",&type); // for(int i=1;i<=n;i++) printf("%d ",query(1,1,n,i,i)); // printf("\n"); if(type=='F') { int x; scanf("%d",&x); if(x==st) printf("0\n"); else if(x>st) { int mx = query(st+1,x); int l = 1, r = st-1, mid, res = st; while(l<=r) { mid = (l+r)/2; if(query(mid,st-1)<=mx) { res = mid; r = mid-1; } else l = mid+1; } printf("%d\n",x-res); } else { int mx = query(x,st-1); int l = st+1, r = n, mid, res = st; while(l<=r) { mid = (l+r)/2; if(query(st+1,mid)<=mx) { res = mid; l = mid+1; } else r = mid-1; } printf("%d\n",res-x); } } else { int x,ra; scanf("%d%d",&x,&ra); for(int i=ra-1;i>=1;i--) update(pos[i],query(pos[i],pos[i])+1); update(x,query(pos[ra],pos[ra])+1); int hey = 15; for(int i=1;i<=15;i++) if(pos[i]==x) hey = i; for(int i=hey;i>=ra;i--) pos[i] = pos[i-1]; pos[ra] = x; // for(int i=1;i<=n;i++) printf("%d ",pos[i]); // printf("\n"); } } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 380 KB | Output is correct |
2 | Correct | 3 ms | 380 KB | Output is correct |
3 | Correct | 2 ms | 436 KB | Output is correct |
4 | Correct | 6 ms | 644 KB | Output is correct |
5 | Correct | 12 ms | 644 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 261 ms | 660 KB | Output is correct |
2 | Correct | 229 ms | 788 KB | Output is correct |
3 | Correct | 200 ms | 792 KB | Output is correct |
4 | Correct | 155 ms | 808 KB | Output is correct |
5 | Correct | 243 ms | 1100 KB | Output is correct |
6 | Correct | 249 ms | 1100 KB | Output is correct |
7 | Correct | 220 ms | 1120 KB | Output is correct |
8 | Correct | 166 ms | 1120 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 144 ms | 2724 KB | Output is correct |
2 | Correct | 112 ms | 2724 KB | Output is correct |
3 | Correct | 110 ms | 2724 KB | Output is correct |
4 | Correct | 2 ms | 2724 KB | Output is correct |
5 | Correct | 184 ms | 5096 KB | Output is correct |
6 | Correct | 212 ms | 5136 KB | Output is correct |
7 | Correct | 153 ms | 5136 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 35 ms | 5136 KB | Output is correct |
2 | Correct | 34 ms | 5136 KB | Output is correct |
3 | Correct | 82 ms | 5136 KB | Output is correct |
4 | Correct | 87 ms | 5136 KB | Output is correct |
5 | Correct | 102 ms | 5136 KB | Output is correct |
6 | Correct | 131 ms | 5136 KB | Output is correct |
7 | Correct | 135 ms | 5136 KB | Output is correct |
8 | Correct | 112 ms | 5136 KB | Output is correct |
9 | Correct | 659 ms | 6300 KB | Output is correct |
10 | Correct | 292 ms | 6300 KB | Output is correct |
11 | Correct | 378 ms | 6300 KB | Output is correct |
12 | Correct | 609 ms | 6300 KB | Output is correct |
13 | Correct | 597 ms | 6300 KB | Output is correct |