oj.uz

Submission #25947

# Submission time Handle Problem Language Result Execution time Memory
25947 2017-06-25T07:46:51 Z 서규호(#1088) Cake (CEOI14_cake) C++14
20 / 100
 2000 ms 3000 KB 
#include <bits/stdc++.h>

#define lld long long
#define pp pair<int,int>
#define pb push_back
#define MOD 1000000007
#define left lleft
#define right rright
#define INF 2000000000
#define Linf 1000000000000000000LL
#define next nnext
#define minus mminus

using namespace std;

int N,M,Q,K;
int a[250002];
int where[12],next[12];

int get(int x){
	if(x <= M) return a[x]-x;
	else return a[x]+x;
}
void change(int s,int e,int value){
	for(int i=s; i<=e; i++) a[i] = value;
}

int main(){
	scanf("%d %d",&N,&M);
	K = min(10,N); where[K+1] = N+1;
	for(int i=1; i<=N; i++){
		scanf("%d",&a[i]);
		for(int j=1; j<=K; j++){
			if(a[where[j]] < a[i]){
				for(int k=K; k>=j+1; k--) where[k] = where[k-1];
				where[j] = i;
				break;
			}
		}
	}
	int l,r;
	l = M; r = M; a[M] = 0;
	while(r-l != N-1){
		if(l == 1){
			r++;
			a[r] = r-l;
		}else if(r == N){
			l--;
			a[l] = r-l;
		}else if(a[l-1] < a[r+1]){
			l--;
			a[l] = r-l;
		}else{
			r++;
			a[r] = r-l;
		}
	}
	for(int i=1; i<=N; i++){
		if(i <= M) a[i] += i;
		else a[i] -= i;
	}
	scanf("%d",&Q);
	for(int i=1; i<=Q; i++){
		int x,y,t,t2;
		char op[3];
		scanf("%s %d",op,&x);
		if(op[0] == 'F'){
			printf("%d\n",get(x));
		}else{
			scanf("%d",&y);
			if(x == M) continue;
			t = -1;
			for(int j=1; j<=K; j++){
				if(where[j] == x){
					t = j;
					break;
				}
			}
			if(t == -1){
				for(int j=K; j>=y+1; j--) where[j] = where[j-1];
				where[y] = x;
			}else{
				for(int j=t; j>y; j--) where[j] = where[j-1];
				where[y] = x;
			}
			vector<pp> tmp;
			tmp.pb({0,0});
			for(int i=1; i<=K; i++) tmp.pb({where[i],i});
			sort(tmp.begin(),tmp.end());
			tmp.pb({0,K+1});
			for(int i=1; i<=K; i++){
				if(tmp[i].first >= M) break;
				next[tmp[i].second] = tmp[i-1].second;
			}
			for(int i=K; i>=1; i--){
				if(tmp[i].first <= M) break;
				next[tmp[i].second] = tmp[i+1].second;
			}
			if(M < x){
				l = M-(get(x)-(x-M));
				t = t2 = 0;
				for(int j=1; j<y; j++){
					if(where[t] < where[j] && where[j] <= l-1){
						t = j;
					}
				}
				change(where[t]+1,l-1,x-1);
				t2 = y;
			}else{
				r = M+(get(x)-(M-x));
				t = y; t2 = K+1;
				for(int j=1; j<y; j++){
					if(where[t2] > where[j] && where[j] >= r+1){
						t2 = j;
					}
				}
				change(r+1,where[t2]-1,r-x-(r+1));
			}
			while(!(t == 0 && t2 == K+1)){
                if(t == 0 || (t2 != K+1 && t2 > t)){
                    change(where[t2],where[next[t2]]-1,where[t2]-where[t]-1-where[t2]);
                    t2 = next[t2];
                }else{
                    change(where[next[t]]+1,where[t],where[t2]-where[t]-1+where[t]);
                    t = next[t];
                }
            }
		}
	}

	return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:29:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
                      ^
cake.cpp:32:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^
cake.cpp:62:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&Q);
                ^
cake.cpp:66:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s %d",op,&x);
                       ^
cake.cpp:70:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&y);
                  ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3000 KB Output is correct
2 Correct 0 ms 3000 KB Output is correct
3 Correct 0 ms 3000 KB Output is correct
4 Incorrect 3 ms 3000 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 3000 KB Execution timed out
2 Execution timed out 2000 ms 3000 KB Execution timed out
3 Execution timed out 2000 ms 3000 KB Execution timed out
4 Execution timed out 2000 ms 3000 KB Execution timed out
5 Execution timed out 2000 ms 3000 KB Execution timed out
6 Execution timed out 2000 ms 3000 KB Execution timed out
7 Execution timed out 2000 ms 3000 KB Execution timed out
8 Execution timed out 2000 ms 3000 KB Execution timed out

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 3000 KB Output is correct
2 Correct 66 ms 3000 KB Output is correct
3 Correct 56 ms 3000 KB Output is correct
4 Correct 0 ms 3000 KB Output is correct
5 Correct 86 ms 3000 KB Output is correct
6 Correct 89 ms 3000 KB Output is correct
7 Correct 86 ms 3000 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 3000 KB Output isn't correct
2 Incorrect 76 ms 3000 KB Output isn't correct
3 Incorrect 619 ms 3000 KB Output isn't correct
4 Correct 719 ms 3000 KB Output is correct
5 Incorrect 179 ms 3000 KB Output isn't correct
6 Correct 1746 ms 3000 KB Output is correct
7 Correct 473 ms 3000 KB Output is correct
8 Execution timed out 2000 ms 3000 KB Execution timed out
9 Execution timed out 2000 ms 3000 KB Execution timed out
10 Incorrect 469 ms 3000 KB Output isn't correct
11 Correct 1893 ms 3000 KB Output is correct
12 Execution timed out 2000 ms 3000 KB Execution timed out
13 Execution timed out 2000 ms 3000 KB Execution timed out