Submission #676495

#	Time	Username	Problem	Language	Result	Execution time	Memory
676495		penguin133	Cake (CEOI14_cake)	C++17	100 / 100	1110 ms	33764 KiB

cake

#include <bits/stdc++.h>
using namespace std;
struct node{
	int s,e,m,val,lazy;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e)/2;
		val = 0, lazy = 0;
		if(s != e)l = new node(s, m), r= new node(m+1, e);
	}
	void update(int p, int v){
		if(s == e)val+=v;
		else{
			if(p <= m)l->update(p,v);
			else r->update(p,v);
			val = max(l->val, r->val);
		}
	}
	int query(int a, int b){
		if(s == a && b == e)return val;
		else if(b <= m)return l->query(a,b);
		else if(a > m)return r->query(a,b);
		else return max(l->query(a,m), r->query(m+1,b));
	}
}*root;
pair<int, int> A[250005];
vector<pair<int, int> > v, tmp;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n,k;
	cin >> n >> k;
	root = new node(1, n);
	for(int i=1;i<=n;i++){
		int x;cin >> x;
		root->update(i, x);
		A[i] = {x,i};
	}
	sort(A+1, A+n+1, greater<pair<int, int> > ());
	for(int i=1;i<=min(n ,10);i++)v.push_back(A[i]);
	int q;cin >> q;
	while(q--){
		char c; int a,b;
		cin >> c;
		if(c == 'E'){
			tmp.clear();
			cin >> a >> b;
			pair<int, int> tmp2 = v[b-1];
			if(tmp2.second != a){
				root->update(a, tmp2.first + 1 - root->query(a,a));
				//cout << root->query(a,a) << " upd\n";
				while(!v.empty() && v.back() != tmp2)tmp.push_back(v.back()), v.pop_back();
				tmp.push_back(tmp2);
				if(!v.empty())v.pop_back();
				reverse(tmp.begin(), tmp.end());
				v.push_back({tmp2.first + 1, a});
				for(auto i: tmp){
					if(i.second == a)continue;
					if(v.size() == min(n,10))break;
					v.push_back(i);
				}
				for(int i= v.size()-2;i>=0;i--){
					if(v[i].first == v[i+1].first){
						root->update(v[i].second, 1);
						v[i].first++;
					}
				}
			}
		}
		else{
			cin >> a;
			if(a == k)cout << "0\n";
			if(a > k){
				int s = 1, e = k - 1, ans = k;
				int x = root->query(k+1, a);
				while(s <= e){
					int m = (s + e)/2;
					if(root->query(m, k-1) < x)ans = m, e = m - 1;
					else s = m + 1;
				}
				cout << a-ans << '\n';
			}
			else if(a < k){
				int s = k + 1, e = n , ans = k;
				int x = root->query(a, k-1);
				while(s <= e){
					int m = (s + e)/2;
					if(root->query(k+1, m) < x)ans= m , s = m  +1;
					else e = m - 1;
				}
				cout << ans-a << '\n';
			}
		}
	}
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:58:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   58 |      if(v.size() == min(n,10))break;
      |         ~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50