oj.uz

Submission #385261

# Submission time Handle Problem Language Result Execution time Memory
385261 2021-04-03T21:43:24 Z ritul_kr_singh Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 26220 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); }
};


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 *= 1e7);
	}
	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;
			b.erase(a[x]);
			auto f = b.rbegin();
			for(int j=1; j<y; ++j) --f;
			a[x] = (*f)+1;
			st.update(x, a[x]);
		}else{
			if(x==s) cout << 0 nl;
			else if(x>s){
				if(s==0) cout << x nl;
				else{
					int res = st.get0(s-1, a[x]) + 1;
					cout << x - res nl;
				}
			}else{
				if(s==n-1) cout << n-1-x nl;
				else{
					int res = st.get1(s+1, a[x]) - 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 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 185 ms 5516 KB Output isn't correct
2 Incorrect 175 ms 5612 KB Output isn't correct
3 Incorrect 173 ms 5612 KB Output isn't correct
4 Incorrect 178 ms 5612 KB Output isn't correct
5 Incorrect 215 ms 6892 KB Output isn't correct
6 Incorrect 209 ms 7276 KB Output isn't correct
7 Incorrect 211 ms 7168 KB Output isn't correct
8 Incorrect 206 ms 7276 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 9836 KB Output isn't correct
2 Incorrect 88 ms 9708 KB Output isn't correct
3 Incorrect 68 ms 9580 KB Output isn't correct
4 Execution timed out 2081 ms 364 KB Time limit exceeded
5 Incorrect 227 ms 21256 KB Output isn't correct
6 Incorrect 228 ms 21356 KB Output isn't correct
7 Incorrect 110 ms 21100 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 1132 KB Output isn't correct
2 Incorrect 21 ms 1260 KB Output isn't correct
3 Incorrect 66 ms 5228 KB Output isn't correct
4 Incorrect 60 ms 5228 KB Output isn't correct
5 Execution timed out 2089 ms 876 KB Time limit exceeded
6 Incorrect 126 ms 8044 KB Output isn't correct
7 Incorrect 81 ms 3276 KB Output isn't correct
8 Incorrect 181 ms 10384 KB Output isn't correct
9 Incorrect 611 ms 26220 KB Output isn't correct
10 Execution timed out 2068 ms 876 KB Time limit exceeded
11 Incorrect 205 ms 7532 KB Output isn't correct
12 Incorrect 541 ms 22892 KB Output isn't correct
13 Incorrect 471 ms 26160 KB Output isn't correct