oj.uz

Submission #25939

# Submission time Handle Problem Language Result Execution time Memory
25939 2017-06-25T07:29:18 Z 김동현(#1086) Cake (CEOI14_cake) C++14
0 / 100
 753 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());
		}
		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 579 ms 5048 KB Output isn't correct
2 Correct 349 ms 5048 KB Output is correct
3 Incorrect 433 ms 5048 KB Output isn't correct
4 Correct 183 ms 5048 KB Output is correct
5 Incorrect 476 ms 5048 KB Output isn't correct
6 Correct 453 ms 5048 KB Output is correct
7 Incorrect 483 ms 5048 KB Output isn't correct
8 Correct 186 ms 5048 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 5048 KB Output isn't correct
2 Incorrect 103 ms 5048 KB Output isn't correct
3 Correct 66 ms 5048 KB Output is correct
4 Correct 0 ms 5048 KB Output is correct
5 Incorrect 129 ms 5048 KB Output isn't correct
6 Incorrect 136 ms 5048 KB Output isn't correct
7 Correct 149 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 46 ms 5048 KB Output isn't correct
3 Incorrect 76 ms 5048 KB Output isn't correct
4 Incorrect 99 ms 5048 KB Output isn't correct
5 Incorrect 189 ms 5048 KB Output isn't correct
6 Incorrect 139 ms 5048 KB Output isn't correct
7 Incorrect 166 ms 5048 KB Output isn't correct
8 Incorrect 176 ms 5048 KB Output isn't correct
9 Incorrect 583 ms 5048 KB Output isn't correct
10 Incorrect 563 ms 5048 KB Output isn't correct
11 Incorrect 619 ms 5048 KB Output isn't correct
12 Incorrect 753 ms 5048 KB Output isn't correct
13 Incorrect 639 ms 5048 KB Output isn't correct