oj.uz

Submission #676495

# Submission time Handle Problem Language Result Execution time Memory
676495 2022-12-31T03:44:09 Z penguin133 Cake (CEOI14_cake) C++17
100 / 100
 1110 ms 33764 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 14 ms 1488 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 5564 KB Output is correct
2 Correct 172 ms 5664 KB Output is correct
3 Correct 185 ms 5660 KB Output is correct
4 Correct 131 ms 5708 KB Output is correct
5 Correct 232 ms 7412 KB Output is correct
6 Correct 225 ms 7756 KB Output is correct
7 Correct 210 ms 7704 KB Output is correct
8 Correct 156 ms 7832 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 12528 KB Output is correct
2 Correct 157 ms 12436 KB Output is correct
3 Correct 157 ms 12172 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 319 ms 28824 KB Output is correct
6 Correct 307 ms 28796 KB Output is correct
7 Correct 233 ms 28540 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 1056 KB Output is correct
2 Correct 45 ms 1348 KB Output is correct
3 Correct 117 ms 6436 KB Output is correct
4 Correct 124 ms 6476 KB Output is correct
5 Correct 112 ms 1860 KB Output is correct
6 Correct 228 ms 9068 KB Output is correct
7 Correct 158 ms 3372 KB Output is correct
8 Correct 134 ms 13024 KB Output is correct
9 Correct 1110 ms 33668 KB Output is correct
10 Correct 364 ms 5200 KB Output is correct
11 Correct 546 ms 7896 KB Output is correct
12 Correct 1055 ms 28320 KB Output is correct
13 Correct 864 ms 33764 KB Output is correct