oj.uz

Submission #65926

# Submission time Handle Problem Language Result Execution time Memory
65926 2018-08-09T06:10:31 Z ikura355 Cake (CEOI14_cake) C++14
100 / 100
 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

cake.cpp: In function 'int main()':
cake.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&st);
  ~~~~~^~~~~~~~~~~~~~~
cake.cpp:40:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
                        ~~~~~^~~~~~~~~~~~
cake.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
cake.cpp:48:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char type; scanf(" %c",&type);
              ~~~~~^~~~~~~~~~~~~
cake.cpp:52:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x; scanf("%d",&x);
           ~~~~~^~~~~~~~~
cake.cpp:82:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x,ra; scanf("%d%d",&x,&ra);
              ~~~~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory 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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory 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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory 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

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory 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