Submission #25948

#	Time	Username	Problem	Language	Result	Execution time	Memory
25948		kdh9949	Cake (CEOI14_cake)	C++14	100 / 100	706 ms	5048 KiB

cake

#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 (stderr)

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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50