oj.uz

Submission #65906

# Submission time Handle Problem Language Result Execution time Memory
65906 2018-08-09T05:48:14 Z ikura355 Cake (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 20224 KB 
#include<bits/stdc++.h>
using namespace std;

const int maxn = 250000 + 5;

int n,st,q;
int a[maxn];
int pos[maxn];
int seg[maxn*4];

void update(int pos, int l, int r, int x, int val) {
    if(l>r || r<x || x<l) return ;
    if(l==r) {
        seg[pos] = val;
        return ;
    }
    int mid = (l+r)/2;
    update(pos<<1,l,mid,x,val); update(pos<<1|1,mid+1,r,x,val);
    seg[pos] = max(seg[pos<<1], seg[pos<<1|1]);
}

int query(int pos, int l, int r, int x, int y) {
    if(l>r || r<x || y<l) return 0;
    if(x<=l && r<=y) return seg[pos];
    int mid = (l+r)/2;
    return max(query(pos<<1,l,mid,x,y), query(pos<<1|1,mid+1,r,x,y));
}

int main() {
	scanf("%d%d",&n,&st);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) {
        pos[n-a[i]+1] = i;
        update(1,1,n,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(1,1,n,st+1,x);
				int l = 1, r = st-1, mid, res = st;
				while(l<=r) {
                    mid = (l+r)/2;
                    if(query(1,1,n,mid,st-1)<=mx) {
                        res = mid;
                        r = mid-1;
                    }
                    else l = mid+1;
				}
				printf("%d\n",x-res);
			}
			else {
				int mx = query(1,1,n,x,st-1);
				int l = st+1, r = n, mid, res = st;
				while(l<=r) {
                    mid = (l+r)/2;
                    if(query(1,1,n,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(1,1,n,pos[i],query(1,1,n,pos[i],pos[i])+1);
			update(1,1,n,x,query(1,1,n,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:30: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:31: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:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
cake.cpp:38: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:42: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:72: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 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 14 ms 724 KB Output is correct
5 Correct 27 ms 892 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 664 ms 892 KB Output is correct
2 Correct 427 ms 892 KB Output is correct
3 Correct 471 ms 892 KB Output is correct
4 Correct 283 ms 892 KB Output is correct
5 Correct 760 ms 1112 KB Output is correct
6 Correct 635 ms 1112 KB Output is correct
7 Correct 543 ms 1112 KB Output is correct
8 Correct 323 ms 1112 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 3248 KB Output is correct
2 Correct 359 ms 3248 KB Output is correct
3 Correct 422 ms 3248 KB Output is correct
4 Correct 3 ms 3248 KB Output is correct
5 Correct 525 ms 6144 KB Output is correct
6 Correct 713 ms 6764 KB Output is correct
7 Correct 527 ms 6764 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 6764 KB Output is correct
2 Correct 109 ms 6764 KB Output is correct
3 Correct 244 ms 6764 KB Output is correct
4 Correct 237 ms 6764 KB Output is correct
5 Correct 252 ms 6764 KB Output is correct
6 Correct 547 ms 6764 KB Output is correct
7 Correct 364 ms 6764 KB Output is correct
8 Correct 318 ms 6764 KB Output is correct
9 Correct 1992 ms 11948 KB Output is correct
10 Correct 840 ms 11948 KB Output is correct
11 Correct 1231 ms 11948 KB Output is correct
12 Correct 1928 ms 15852 KB Output is correct
13 Execution timed out 2060 ms 20224 KB Time limit exceeded