oj.uz

Submission #385392

# Submission time Handle Problem Language Result Execution time Memory
385392 2021-04-04T06:31:58 Z ritul_kr_singh Cake (CEOI14_cake) C++17
100 / 100
 675 ms 7652 KB 
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define nl << '\n'
#define sp << ' ' <<

struct SegmentTree{
	vector<int> a; int sz = 1, ID = -1e9;
	SegmentTree(vector<int> &v){
		while(sz < (int)v.size()) sz += sz;
		a.resize(2*sz, ID);
		build(v, 0, 0, sz);
	}
	void build(vector<int> &v, int x, int lx, int rx){
		if(rx-lx==1){
			if(lx<(int)v.size()) a[x] = v[lx];
			return;
		}
		int mx = (lx+rx)/2;
		build(v, 2*x+1, lx, mx);
		build(v, 2*x+2, mx, rx);
		a[x] = max(a[2*x+1], a[2*x+2]);
	}
	void update(int i, int val, int x, int lx, int rx){
		if(rx-lx==1) return void(a[x] = val);
		int mx = (lx+rx)/2;
		if(i<mx) update(i, val, 2*x+1, lx, mx);
		else update(i, val, 2*x+2, mx, rx);
		a[x] = max(a[2*x+1], a[2*x+2]);
	}
	void update(int i, int val){ update(i, val, 0, 0, sz); }
	int get0(int r, int val, int x, int lx, int rx){
		if(r<=lx) return -1;
		if(rx-lx==1) return (a[x] > val ? lx : -1);
		int mx = (lx+rx)/2;
		int res;
		if(a[2*x+2]>val){
			res = get0(r, val, 2*x+2, mx, rx);
			if(res>=0) return res;
		}
		if(a[2*x+1]>val){
			res = get0(r, val, 2*x+1, lx, mx);
			if(res>=0) return res;
		}
		return -1;
	}
	int get0(int r, int val){ return get0(r+1, val, 0, 0, sz); }
	int get1(int l, int val, int x, int lx, int rx){
		if(rx<=l) return -1;
		if(rx-lx==1) return (a[x] > val ? lx : -1);
		int mx = (lx+rx)/2;
		int res;
		if(a[2*x+1]>val){
			res = get1(l, val, 2*x+1, lx, mx);
			if(res>=0) return res;
		}
		if(a[2*x+2]>val){
			res = get1(l, val, 2*x+2, mx, rx);
			if(res>=0) return res;
		}
		return -1;
	}
	int get1(int l, int val){ return get1(l, val, 0, 0, sz); }
	int get(int l, int r, int x, int lx, int rx){
		if(r<=lx or rx<=l) return ID;
		if(l<=lx and rx<=r) return a[x];
		int mx = (lx+rx)/2;
		return max(get(l, r, 2*x+1, lx, mx), get(l, r, 2*x+2, mx, rx));
	}
	int get(int l, int r){ return get(l, r+1, 0, 0, sz); }
};


signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, s; cin >> n >> s; --s;
	vector<int> a(n);
	vector<array<int, 2>> b;
	for(int i=0; i<n; ++i){
		cin >> a[i];
		b.push_back({a[i], i});
	}
	sort(b.rbegin(), b.rend());
	while(b.size()>10) b.pop_back();
	SegmentTree st(a);

	int q, x, y; cin >> q;
	char type;
	for(int i=1; i<=q; ++i){
		cin >> type >> x; --x;
		if(type=='E'){
			cin >> y;
			int curr = -1;
			for(int i=0; i+1<y; ++i){
				curr = b[i][0];
				b[i][0]++;
				a[b[i][1]]++;
				st.update(b[i][1], b[i][0]);
			}
			if(curr<0) curr = b[0][0]+1;
			bool found = false;
			for(int i=0; i<10; ++i){
				if(b[i][1]==x){
					found = true;
					b.erase(b.begin()+i);
					break;
				}
			}
			if(!found) b.pop_back();
			a[x] = curr;
			st.update(x, curr);
			b.push_back({a[x], x});
			sort(b.rbegin(), b.rend());
		}else{
			if(x==s) cout << 0 nl;
			else if(x>s){
				if(s==0) cout << x nl;
				else{
					int xx = st.get(s+1, x);
					int res = st.get0(s-1, xx) + 1;
					cout << x - res nl;
				}
			}else{
				if(s==n-1) cout << n-1-x nl;
				else{
					int xx = st.get(x, s-1);
					int res = st.get1(s+1, xx) - 1;
					if(res<0) res = n-1;
					cout << res-x nl;
				}
			}
		}
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 5 ms 492 KB Output is correct
5 Correct 12 ms 748 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 1132 KB Output is correct
2 Correct 277 ms 1180 KB Output is correct
3 Correct 297 ms 1180 KB Output is correct
4 Correct 222 ms 1132 KB Output is correct
5 Correct 425 ms 1640 KB Output is correct
6 Correct 368 ms 1512 KB Output is correct
7 Correct 322 ms 1512 KB Output is correct
8 Correct 230 ms 1640 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 3944 KB Output is correct
2 Correct 82 ms 3944 KB Output is correct
3 Correct 72 ms 3944 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 127 ms 7012 KB Output is correct
6 Correct 117 ms 6884 KB Output is correct
7 Correct 115 ms 6756 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1004 KB Output is correct
2 Correct 33 ms 972 KB Output is correct
3 Correct 66 ms 2540 KB Output is correct
4 Correct 86 ms 2540 KB Output is correct
5 Correct 111 ms 1132 KB Output is correct
6 Correct 120 ms 3560 KB Output is correct
7 Correct 121 ms 1460 KB Output is correct
8 Correct 166 ms 3048 KB Output is correct
9 Correct 675 ms 7524 KB Output is correct
10 Correct 357 ms 1912 KB Output is correct
11 Correct 451 ms 2792 KB Output is correct
12 Correct 626 ms 6900 KB Output is correct
13 Correct 514 ms 7652 KB Output is correct