oj.uz

Submission #90735

# Submission time Handle Problem Language Result Execution time Memory
90735 2018-12-24T07:58:28 Z Dat160601 Cake (CEOI14_cake) C++17
0 / 100
 586 ms 96336 KB 
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#pragma GCC optimize("O3")

int n, q, ps, a[250007], x, y, szlef, szrig;
char type;

int read(){
	char p;
	while((p = getchar())){
		if(p < '0' || p > '9') continue;
		break;
	}
	int ret = p - '0';
	while((p = getchar())){
		if(p >= '0' && p <= '9'){
			ret *= 10;
			ret += p - '0';
		}
		else break;
	}
	return ret;
}

struct segtree{
	int it[1000007];

	segtree(){
		memset(it, 0, sizeof(it));
	}

	void update(int k, int l, int r, int pos, int val){
		if(l > pos || r < pos) return;
		if(l == r){
			it[k] = val;
			return;
		}
		int mid = (l + r) >> 1;
		update(k << 1, l, mid, pos, val);
		update(k << 1 | 1, mid + 1, r, pos, val);
		it[k] = max(it[k << 1], it[k << 1 | 1]);
	}

	int get(int k, int l, int r, int L, int R){
		if(l > R || r < L || L > R) return 0;
		if(l >= L && r <= R) return it[k];
		int mid = (l + r) >> 1;
		return max(get(k << 1, l, mid, L, R), get(k << 1 | 1, mid + 1, r, L, R));
	}

	int get_pos(int k, int l, int r, int val){
		int mid = (l + r) >> 1;
		if(it[k] <= val) return r;
		if(l == r) return l - 1;
		if(it[k << 1] > val) return get_pos(k << 1, l, mid, val);
		else return get_pos(k << 1 | 1, mid + 1, r, val);
	}
};

segtree lef = segtree(), rig = segtree();
set < pair <int, int> > st;

int main(){
	#ifdef Dat
		freopen("test.in", "r", stdin);
		freopen("test.out", "w", stdout);
	#endif
	n = read(), ps = read();
	szlef = ps - 1;
	szrig = n - ps;
	for(int i = 1; i <= n; i++){
		a[i] = read();
		if(i < ps) lef.update(1, 1, szlef, szlef - i + 1, a[i]);
		else if(i > ps) rig.update(1, 1, szrig, i - ps, a[i]);
		if(i != ps){
			st.insert(mp(a[i], i));
			while((int)st.size() > 10) st.erase(st.begin());
		}
	}
	int cnt = n;
	//lef.update(1, 1, szlef, szlef, 1e9);
	//rig.update(1, 1, szrig, szrig, 1e9);
	q = read();
	while(q --){
		while((type = getchar())){
			if(type == 'E' || type == 'F') break;
		}
		if(type == 'E'){
			x = read(); y = read();
			if(x == ps) continue;
            cnt = a[(*st.rbegin()).se];
            vector <int> sv;
            for(int i = 1; i < y; i++){
				auto iter = st.rbegin();
				int p = (*iter).se;
				st.erase(*iter);
				sv.pb(p);
				a[p] = cnt + y - i + 1;
				if(p < ps) lef.update(1, 1, szlef, szlef - p + 1, a[p]);
				else rig.update(1, 1, szrig, p - ps, a[p]);
            }
            st.erase(mp(a[x], x));
            a[x] = cnt + 1;
			if(x < ps) lef.update(1, 1, szlef, szlef - x + 1, a[x]);
			else rig.update(1, 1, szrig, x - ps, a[x]);
			st.insert(mp(a[x], x));
			for(int p : sv) st.insert(mp(a[p], p));
			while((int)st.size() > 10) st.erase(st.begin());
		}
		else{
			x = read();
			if(x == ps){
				printf("0\n");
			}
			else if(x < ps){
				int val = lef.get(1, 1, szlef, 1, szlef + 1 - x);
				int add = 1 + rig.get_pos(1, 1, szrig, val);
				add += ps - x - 1;
				printf("%d\n", add);
			}
			else{
				int val = rig.get(1, 1, szrig, 1, x - ps);
				int add = 1 + lef.get_pos(1, 1, szlef, val);
				add += x - ps - 1;
				printf("%d\n", add);
			}
		}
	}
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8184 KB Output is correct
2 Correct 8 ms 8268 KB Output is correct
3 Correct 8 ms 8268 KB Output is correct
4 Incorrect 12 ms 8280 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 12860 KB Output is correct
2 Incorrect 188 ms 17312 KB Output isn't correct
3 Correct 237 ms 21904 KB Output is correct
4 Correct 100 ms 26320 KB Output is correct
5 Correct 396 ms 31052 KB Output is correct
6 Incorrect 333 ms 36144 KB Output isn't correct
7 Correct 257 ms 41152 KB Output is correct
8 Correct 108 ms 46076 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 48296 KB Output is correct
2 Incorrect 56 ms 49536 KB Output isn't correct
3 Incorrect 52 ms 50772 KB Output isn't correct
4 Correct 8 ms 50772 KB Output is correct
5 Correct 103 ms 54080 KB Output is correct
6 Correct 87 ms 56580 KB Output is correct
7 Incorrect 87 ms 58820 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 58820 KB Output isn't correct
2 Incorrect 32 ms 58820 KB Output isn't correct
3 Incorrect 57 ms 59636 KB Output isn't correct
4 Correct 85 ms 60612 KB Output is correct
5 Incorrect 117 ms 61536 KB Output isn't correct
6 Correct 97 ms 63540 KB Output is correct
7 Correct 102 ms 64932 KB Output is correct
8 Correct 140 ms 67456 KB Output is correct
9 Correct 570 ms 76108 KB Output is correct
10 Incorrect 367 ms 78160 KB Output isn't correct
11 Correct 442 ms 82668 KB Output is correct
12 Correct 586 ms 89512 KB Output is correct
13 Correct 452 ms 96336 KB Output is correct