oj.uz

Submission #25936

# Submission time Handle Problem Language Result Execution time Memory
25936 2017-06-25T07:16:29 Z 김동현(#1086) Cake (CEOI14_cake) C++14
0 / 100
 683 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] > x) 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());
		}
		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:84: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 Correct 0 ms 5048 KB Output is correct
2 Incorrect 0 ms 5048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 453 ms 5048 KB Output isn't correct
2 Incorrect 326 ms 5048 KB Output isn't correct
3 Incorrect 423 ms 5048 KB Output isn't correct
4 Correct 223 ms 5048 KB Output is correct
5 Incorrect 539 ms 5048 KB Output isn't correct
6 Incorrect 479 ms 5048 KB Output isn't correct
7 Incorrect 459 ms 5048 KB Output isn't correct
8 Correct 209 ms 5048 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 5048 KB Output isn't correct
2 Incorrect 93 ms 5048 KB Output isn't correct
3 Incorrect 69 ms 5048 KB Output isn't correct
4 Correct 0 ms 5048 KB Output is correct
5 Incorrect 149 ms 5048 KB Output isn't correct
6 Incorrect 129 ms 5048 KB Output isn't correct
7 Correct 129 ms 5048 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 5048 KB Output isn't correct
2 Incorrect 39 ms 5048 KB Output isn't correct
3 Incorrect 86 ms 5048 KB Output isn't correct
4 Incorrect 93 ms 5048 KB Output isn't correct
5 Incorrect 153 ms 5048 KB Output isn't correct
6 Incorrect 156 ms 5048 KB Output isn't correct
7 Incorrect 143 ms 5048 KB Output isn't correct
8 Incorrect 203 ms 5048 KB Output isn't correct
9 Incorrect 683 ms 5048 KB Output isn't correct
10 Incorrect 573 ms 5048 KB Output isn't correct
11 Incorrect 569 ms 5048 KB Output isn't correct
12 Incorrect 676 ms 5048 KB Output isn't correct
13 Incorrect 599 ms 5048 KB Output isn't correct