oj.uz

Submission #385388

# Submission time Handle Problem Language Result Execution time Memory
385388 2021-04-04T06:29:58 Z ritul_kr_singh Cake (CEOI14_cake) C++17
75 / 100
 722 ms 7396 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);
			}
			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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 620 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 680 KB Output is correct
2 Correct 285 ms 680 KB Output is correct
3 Correct 314 ms 680 KB Output is correct
4 Correct 222 ms 620 KB Output is correct
5 Correct 416 ms 1076 KB Output is correct
6 Correct 385 ms 1000 KB Output is correct
7 Correct 318 ms 1128 KB Output is correct
8 Correct 234 ms 1128 KB Output is correct

Subtask #3
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 3304 KB Output is correct
2 Correct 95 ms 3176 KB Output is correct
3 Correct 71 ms 3176 KB Output is correct
4 Runtime error 2 ms 620 KB Execution killed with signal 11
5 Correct 134 ms 6116 KB Output is correct
6 Correct 120 ms 6116 KB Output is correct
7 Correct 116 ms 5860 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 768 KB Output is correct
2 Correct 39 ms 620 KB Output is correct
3 Correct 64 ms 1772 KB Output is correct
4 Correct 84 ms 1900 KB Output is correct
5 Correct 107 ms 748 KB Output is correct
6 Correct 121 ms 2792 KB Output is correct
7 Correct 120 ms 1388 KB Output is correct
8 Correct 172 ms 3052 KB Output is correct
9 Correct 643 ms 7396 KB Output is correct
10 Correct 355 ms 1796 KB Output is correct
11 Correct 461 ms 2572 KB Output is correct
12 Correct 722 ms 6736 KB Output is correct
13 Correct 535 ms 7388 KB Output is correct