oj.uz

Submission #25937

# Submission time Handle Problem Language Result Execution time Memory
25937 2017-06-25T07:26:14 Z 김동현(#1086) Cake (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

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 5048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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