oj.uz

Submission #25942

# Submission time Handle Problem Language Result Execution time Memory
25942 2017-06-25T07:35:22 Z 김동현(#1086) Cake (CEOI14_cake) C++14
100 / 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){
		int x;
		if(t == 0){
			for(x = p + 1 + sz; __builtin_popcount(x + 1) != 1; x = (x + 1) / 2){
				if(dat[x] > v) break;
			}
		}
		else{
			for(x = p - 1 + sz; __builtin_popcount(x) != 1; x = (x - 1) / 2){
				if(dat[x] > v) break;
			}
		}
		for(; x < sz; ){
			if(dat[2 * x + t] > v) x = 2 * x + t;
			else x = 2 * x + !t;
		}
		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());
	}
	S.upd(0, (int)1e9);
	S.upd(n + 1, (int)1e9);
	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:51: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:53:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
                     ^
cake.cpp:60:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
                 ^
cake.cpp:62: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:64: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:82:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
                   ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5048 KB Output is correct
2 Correct 0 ms 5048 KB Output is correct
3 Correct 0 ms 5048 KB Output is correct
4 Correct 6 ms 5048 KB Output is correct
5 Correct 9 ms 5048 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 5048 KB Output is correct
2 Correct 349 ms 5048 KB Output is correct
3 Correct 379 ms 5048 KB Output is correct
4 Correct 179 ms 5048 KB Output is correct
5 Correct 539 ms 5048 KB Output is correct
6 Correct 509 ms 5048 KB Output is correct
7 Correct 446 ms 5048 KB Output is correct
8 Correct 203 ms 5048 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 5048 KB Output is correct
2 Correct 89 ms 5048 KB Output is correct
3 Correct 79 ms 5048 KB Output is correct
4 Correct 0 ms 5048 KB Output is correct
5 Correct 146 ms 5048 KB Output is correct
6 Correct 149 ms 5048 KB Output is correct
7 Correct 109 ms 5048 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 5048 KB Output is correct
2 Correct 39 ms 5048 KB Output is correct
3 Correct 69 ms 5048 KB Output is correct
4 Correct 103 ms 5048 KB Output is correct
5 Correct 156 ms 5048 KB Output is correct
6 Correct 139 ms 5048 KB Output is correct
7 Correct 139 ms 5048 KB Output is correct
8 Correct 236 ms 5048 KB Output is correct
9 Correct 753 ms 5048 KB Output is correct
10 Correct 516 ms 5048 KB Output is correct
11 Correct 603 ms 5048 KB Output is correct
12 Correct 619 ms 5048 KB Output is correct
13 Correct 609 ms 5048 KB Output is correct