Submission #65926

#	Time	Username	Problem	Language	Result	Execution time	Memory
65926		ikura355	Cake (CEOI14_cake)	C++14	100 / 100	659 ms	6300 KiB

cake

#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 (stderr)

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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50