oj.uz

Submission #385386

# Submission time Handle Problem Language Result Execution time Memory
385386 2021-04-04T06:28:45 Z ritul_kr_singh Cake (CEOI14_cake) C++17
75 / 100
 667 ms 12252 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 = -1e18;
	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 420 ms 1000 KB Output is correct
2 Correct 287 ms 1000 KB Output is correct
3 Correct 304 ms 1128 KB Output is correct
4 Correct 221 ms 1000 KB Output is correct
5 Correct 416 ms 1516 KB Output is correct
6 Correct 377 ms 1644 KB Output is correct
7 Correct 329 ms 1644 KB Output is correct
8 Correct 236 ms 1636 KB Output is correct

Subtask #3
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 5476 KB Output is correct
2 Correct 81 ms 5368 KB Output is correct
3 Correct 74 ms 5348 KB Output is correct
4 Runtime error 2 ms 620 KB Execution killed with signal 11
5 Correct 131 ms 11228 KB Output is correct
6 Correct 122 ms 11228 KB Output is correct
7 Correct 114 ms 10972 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 620 KB Output is correct
2 Correct 32 ms 752 KB Output is correct
3 Correct 67 ms 2920 KB Output is correct
4 Correct 87 ms 2920 KB Output is correct
5 Correct 107 ms 748 KB Output is correct
6 Correct 122 ms 4580 KB Output is correct
7 Correct 119 ms 1512 KB Output is correct
8 Correct 177 ms 4964 KB Output is correct
9 Correct 667 ms 12252 KB Output is correct
10 Correct 358 ms 1644 KB Output is correct
11 Correct 479 ms 2924 KB Output is correct
12 Correct 654 ms 11104 KB Output is correct
13 Correct 517 ms 12224 KB Output is correct