oj.uz

Submission #25958

# Submission time Handle Problem Language Result Execution time Memory
25958 2017-06-25T08:13:47 Z 서규호(#1088) Cake (CEOI14_cake) C++14
26.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){
				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:120: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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 3000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1989 ms 3000 KB Output is correct
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
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 3000 KB Output is correct
2 Correct 69 ms 3000 KB Output is correct
3 Correct 53 ms 3000 KB Output is correct
4 Incorrect 0 ms 3000 KB Output isn't correct
5 Correct 89 ms 3000 KB Output is correct
6 Correct 93 ms 3000 KB Output is correct
7 Correct 96 ms 3000 KB Output is correct

Subtask #4
16.666667 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 3000 KB Output is correct
2 Correct 66 ms 3000 KB Output is correct
3 Correct 646 ms 3000 KB Output is correct
4 Correct 703 ms 3000 KB Output is correct
5 Correct 149 ms 3000 KB Output is correct
6 Correct 1693 ms 3000 KB Output is correct
7 Correct 463 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 566 ms 3000 KB Output is correct
11 Correct 1779 ms 3000 KB Output is correct
12 Execution timed out 2000 ms 0 KB Execution timed out
13 Execution timed out 2000 ms 3000 KB Execution timed out