oj.uz

Submission #25948

# Submission time Handle Problem Language Result Execution time Memory
25948 2017-06-25T07:46:52 Z kdh9949 Cake (CEOI14_cake) C++14
100 / 100
 706 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 3 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 513 ms 5048 KB Output is correct
2 Correct 349 ms 5048 KB Output is correct
3 Correct 336 ms 5048 KB Output is correct
4 Correct 229 ms 5048 KB Output is correct
5 Correct 563 ms 5048 KB Output is correct
6 Correct 479 ms 5048 KB Output is correct
7 Correct 416 ms 5048 KB Output is correct
8 Correct 263 ms 5048 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 5048 KB Output is correct
2 Correct 106 ms 5048 KB Output is correct
3 Correct 96 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 136 ms 5048 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 5048 KB Output is correct
2 Correct 46 ms 5048 KB Output is correct
3 Correct 76 ms 5048 KB Output is correct
4 Correct 106 ms 5048 KB Output is correct
5 Correct 146 ms 5048 KB Output is correct
6 Correct 123 ms 5048 KB Output is correct
7 Correct 143 ms 5048 KB Output is correct
8 Correct 183 ms 5048 KB Output is correct
9 Correct 633 ms 5048 KB Output is correct
10 Correct 466 ms 5048 KB Output is correct
11 Correct 613 ms 5048 KB Output is correct
12 Correct 706 ms 5048 KB Output is correct
13 Correct 633 ms 5048 KB Output is correct