oj.uz

답안 #25937

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25937 2017-06-25T07:26:14 Z 김동현(#1086) 케이크 (CEOI14_cake) C++14
0 / 100
 2000 ms 5048 KB 
#include <bits/stdc++.h>
using namespace std;

int n, q, p, a[250010];

struct Dat{
	int i;
	bool operator<(const Dat &oth) const {
		return a[i] < a[oth.i];
	}
};

set<Dat> t10;

const int sz = 262144;
struct Seg{
	int dat[2 * sz];
	void upd(int x, int v){
		x += sz; dat[x] = v;
		for(x /= 2; x; x /= 2) dat[x] = max(dat[2 * x], dat[2 * x + 1]);
	}
	int get(int s, int e){
		int ret = 0;
		for(s += sz, e += sz; s <= e; s /= 2, e /= 2){
			if(s % 2 == 1) ret = max(ret, dat[s++]);
			if(e % 2 == 0) ret = max(ret, dat[e--]);
		}
		return ret;
	}
	int pos(int t, int v){
		//printf("// get %d %d", t, v);
		int x;
		if(t == 0){
			for(x = p + 1 + sz; __builtin_popcount(x + 1) != 1; x = (x + 1) / 2){
				if(dat[x] > v) break;
			}
			if(dat[x] < v){ /*printf(" : %d\n", n + 1);*/ return n + 1; }
		}
		else{
			for(x = p - 1 + sz; __builtin_popcount(x) != 1; x = (x - 1) / 2){
				if(dat[x] > v) break;
			}
			if(dat[x] < v){ /*printf(" : 0\n");*/ return 0; }
		}
		for(; x < sz; ){
			if(dat[2 * x] > v) x = 2 * x;
			else x = 2 * x + 1;
		}
		//printf(" : %d\n", x - sz);
		return x - sz;
	}
} S;

int main(){
	scanf("%d%d", &n, &p);
	for(int i = 1; i <= n; i++){
		scanf("%d", a + i);
		S.upd(i, a[i]);
		t10.insert({i});
		while(t10.size() > 10) t10.erase(t10.begin());
	}
	scanf("%d", &q);
	for(int x, y; q--; ){
		char buf[3]; scanf("%s", buf);
		if(buf[0] == 'E'){
			scanf("%d%d", &x, &y);
			int t = a[(*t10.rbegin()).i];
			vector<int> v;
			for(int i = 0; i < y - 1; i++){
				int u = (*t10.rbegin()).i;
				t10.erase(*t10.rbegin());
				a[u] = t + y - i;
				S.upd(u, a[u]);
				v.push_back(u);
			}
			t10.erase({x});
			a[x] = t + 1;
			S.upd(x, a[x]);
			t10.insert({x});
			for(auto &i : v) t10.insert({i});
			while(t10.size() > 10) t10.erase(t10.begin());
			for(int i = 1; i <= n; i++) printf("%d ", a[i]);
			puts("");
		}
		else{
			scanf("%d", &x);
			if(x < p) printf("%d\n", S.pos(0, S.get(x, p - 1)) - x - 1);
			else if(x == p) puts("0");
			else printf("%d\n", x - S.pos(1, S.get(p + 1, x)) - 1);
		}
	}
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:55:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &p);
                       ^
cake.cpp:57:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
                     ^
cake.cpp:62:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
                 ^
cake.cpp:64:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char buf[3]; scanf("%s", buf);
                                ^
cake.cpp:66:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &x, &y);
                         ^
cake.cpp:86:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
                   ^

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 5048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2000 ms 5048 KB Execution timed out
2 Execution timed out 2000 ms 5048 KB Execution timed out
3 Execution timed out 2000 ms 5048 KB Execution timed out
4 Execution timed out 2000 ms 5048 KB Execution timed out
5 Execution timed out 2000 ms 5048 KB Execution timed out
6 Execution timed out 2000 ms 5048 KB Execution timed out
7 Execution timed out 2000 ms 5048 KB Execution timed out
8 Execution timed out 2000 ms 5048 KB Execution timed out

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 973 ms 5048 KB Output isn't correct
2 Incorrect 953 ms 5048 KB Output isn't correct
3 Incorrect 946 ms 5048 KB Output isn't correct
4 Incorrect 0 ms 5048 KB Output isn't correct
5 Incorrect 1909 ms 5048 KB Output isn't correct
6 Execution timed out 2000 ms 5048 KB Execution timed out
7 Execution timed out 2000 ms 5048 KB Execution timed out

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2000 ms 5048 KB Execution timed out
2 Execution timed out 2000 ms 5048 KB Execution timed out
3 Execution timed out 2000 ms 5048 KB Execution timed out
4 Execution timed out 2000 ms 5048 KB Execution timed out
5 Execution timed out 2000 ms 5048 KB Execution timed out
6 Execution timed out 2000 ms 5048 KB Execution timed out
7 Execution timed out 2000 ms 5048 KB Execution timed out
8 Execution timed out 2000 ms 5048 KB Execution timed out
9 Execution timed out 2000 ms 5048 KB Execution timed out
10 Execution timed out 2000 ms 5048 KB Execution timed out
11 Execution timed out 2000 ms 5048 KB Execution timed out
12 Execution timed out 2000 ms 5048 KB Execution timed out
13 Execution timed out 2000 ms 5048 KB Execution timed out