oj.uz

Submission #25960

# Submission time Handle Problem Language Result Execution time Memory
25960 2017-06-25T08:19:08 Z 서규호(#1088) Cake (CEOI14_cake) C++14
51.6667 / 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);
			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) continue;
			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 if(M > x){
				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);
                  ^
cake.cpp:121:51: warning: 't2' may be used uninitialized in this function [-Wmaybe-uninitialized]
                     change(where[t2],where[next[t2]]-1,where[t2]-where[t]-1-where[t2]);
                                                   ^

Subtask #1
15.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 Correct 3 ms 3000 KB Output is correct
5 Correct 19 ms 3000 KB Output is correct

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 59 ms 3000 KB Output is correct
2 Correct 56 ms 3000 KB Output is correct
3 Correct 46 ms 3000 KB Output is correct
4 Correct 0 ms 3000 KB Output is correct
5 Correct 96 ms 3000 KB Output is correct
6 Correct 93 ms 3000 KB Output is correct
7 Correct 79 ms 3000 KB Output is correct

Subtask #4
16.666667 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 3000 KB Output is correct
2 Correct 73 ms 3000 KB Output is correct
3 Correct 663 ms 3000 KB Output is correct
4 Correct 719 ms 3000 KB Output is correct
5 Correct 146 ms 3000 KB Output is correct
6 Correct 1573 ms 3000 KB Output is correct
7 Correct 446 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 Correct 526 ms 3000 KB Output is correct
11 Correct 1796 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