oj.uz

Submission #385263

# Submission time Handle Problem Language Result Execution time Memory
385263 2021-04-03T22:02:49 Z ritul_kr_singh Cake (CEOI14_cake) C++17
0 / 100
 909 ms 19948 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);
	set<int> b;
	for(int &i : a){
		cin >> i;
		b.insert(i *= 1e12);
	}
	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, prev;
			b.erase(a[x]);
			auto f = b.rbegin();
			if(y==1){
				curr = (*f) + 1e12;
			}else{
				for(int j=1; j+1<y; ++j) --f;
				prev = *f; --f;
				curr = *f;
				curr = (curr+prev)/2;
			}
			a[x] = curr;
			b.insert(a[x]);
			st.update(x, a[x]);
		}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 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 217 ms 1132 KB Output isn't correct
2 Incorrect 219 ms 1132 KB Output isn't correct
3 Incorrect 213 ms 1132 KB Output isn't correct
4 Correct 230 ms 1132 KB Output is correct
5 Incorrect 244 ms 2284 KB Output isn't correct
6 Incorrect 254 ms 2156 KB Output isn't correct
7 Incorrect 239 ms 2156 KB Output isn't correct
8 Correct 256 ms 2156 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 100 ms 8428 KB Output isn't correct
2 Incorrect 86 ms 8428 KB Output isn't correct
3 Incorrect 78 ms 8300 KB Output isn't correct
4 Incorrect 2 ms 364 KB Output isn't correct
5 Incorrect 249 ms 18796 KB Output isn't correct
6 Incorrect 237 ms 19072 KB Output isn't correct
7 Incorrect 125 ms 18688 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 620 KB Output isn't correct
2 Incorrect 29 ms 896 KB Output isn't correct
3 Incorrect 80 ms 4332 KB Output isn't correct
4 Incorrect 83 ms 4332 KB Output isn't correct
5 Incorrect 88 ms 1516 KB Output isn't correct
6 Incorrect 141 ms 6508 KB Output isn't correct
7 Incorrect 101 ms 1644 KB Output isn't correct
8 Incorrect 174 ms 7916 KB Output isn't correct
9 Incorrect 909 ms 19920 KB Output isn't correct
10 Incorrect 286 ms 5100 KB Output isn't correct
11 Incorrect 274 ms 3436 KB Output isn't correct
12 Incorrect 615 ms 17132 KB Output isn't correct
13 Incorrect 546 ms 19948 KB Output isn't correct