oj.uz

Submission #385385

# Submission time Handle Problem Language Result Execution time Memory
385385 2021-04-04T06:27:36 Z ritul_kr_singh Cake (CEOI14_cake) C++17
0 / 100
 716 ms 13024 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.begin(), b.end());
		}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
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 445 ms 1620 KB Output isn't correct
2 Incorrect 279 ms 1640 KB Output isn't correct
3 Incorrect 375 ms 1644 KB Output isn't correct
4 Incorrect 203 ms 1640 KB Output isn't correct
5 Incorrect 479 ms 2252 KB Output isn't correct
6 Incorrect 419 ms 2280 KB Output isn't correct
7 Incorrect 370 ms 2256 KB Output isn't correct
8 Incorrect 226 ms 2260 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 6116 KB Output isn't correct
2 Incorrect 78 ms 6128 KB Output isn't correct
3 Incorrect 76 ms 5988 KB Output isn't correct
4 Runtime error 2 ms 620 KB Execution killed with signal 11
5 Incorrect 160 ms 11740 KB Output isn't correct
6 Incorrect 119 ms 11740 KB Output isn't correct
7 Incorrect 112 ms 11612 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 1004 KB Output isn't correct
2 Incorrect 34 ms 1132 KB Output isn't correct
3 Incorrect 68 ms 3560 KB Output isn't correct
4 Incorrect 91 ms 3560 KB Output isn't correct
5 Incorrect 119 ms 2028 KB Output isn't correct
6 Incorrect 146 ms 5220 KB Output isn't correct
7 Incorrect 133 ms 2152 KB Output isn't correct
8 Incorrect 186 ms 5476 KB Output isn't correct
9 Incorrect 716 ms 12892 KB Output isn't correct
10 Incorrect 382 ms 2924 KB Output isn't correct
11 Incorrect 500 ms 3564 KB Output isn't correct
12 Incorrect 710 ms 11704 KB Output isn't correct
13 Incorrect 555 ms 13024 KB Output isn't correct