oj.uz

답안 #1054495

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1054495 2024-08-12T10:17:55 Z vako_p 케이크 (CEOI14_cake) C++14
30 / 100
 2000 ms 13136 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pb push_back

const int mxN = 1e6;
ll n,a[2 * mxN],idx1[2 * mxN],q,st,mx,last[mxN],idx2[2 * mxN],mx1;

struct segtree{
	vector<pair<ll,ll>> v;
	ll sz = 1;	
	
	void init(){
		while(sz < n) sz *= 2;
		v.assign(2 * sz, {0LL, 0LL});
	}
	
	void set(ll val, ll i, ll x, ll l, ll r){
		if(r - l == 1){
			v[x] = {val, i};
			return;
		}
		ll mid = l + (r - l) / 2;
		if(i < mid) set(val, i, 2 * x + 1, l, mid);
		else set(val, i, 2 * x + 2, mid, r);
		v[x] = max(v[2 * x + 1], v[2 * x + 2]);
	}
	
	void set(ll val, ll i){
		set(val, i, 0, 0, sz);
	}
	
	pair<ll,ll> find(ll l, ll r, ll x, ll lx, ll rx){
		if(lx >= r or rx <= l) return {0, 0};
		if(lx >= l and rx <= r) return v[x];
		ll mid = lx + (rx - lx) / 2;
		return max(find(l, r, 2 * x + 1, lx, mid), find(l, r, 2 * x + 2, mid, rx));
	}
	
	pair<ll,ll> find(ll l, ll r){
		return find(l, r, 0, 0, sz);
	}
	
	pair<ll,ll> find1(ll val, ll l, ll r, ll op, ll x, ll lx, ll rx){
		if(lx >= r or rx <= l) return {-1, -1};
		if(rx - lx == 1){
			if(v[x].first > val) return v[x];
			return {-1, -1};
		}
		ll mid = lx + (rx - lx) / 2;
		pair<ll,ll> ans = find1(val, l, r, op, 2 * x + 1 + op, ((!op) ? (lx) : (mid)), ((!op) ? (mid) : (rx)));
		if(ans.first > val) return ans;
		ans = find1(val, l, r, op, 2 * x + 2 - op, ((!op) ? (mid) : (lx)), ((!op) ? (rx) : (mid)));
		if(ans.first > val) return ans;
		return {-1, -1};
	}
	
	pair<ll,ll> find1(ll val, ll l, ll r, ll op){
		return find1(val, l, r, op, 0, 0, sz);
	}
};
segtree s;

void f(ll idx, ll val){
	if(val == mx){
		a[idx] = ++last[mx];
		idx1[mx] = idx;
		idx2[idx] = mx;
		s.set(a[idx], idx);
		return;
	}
	if(mx1 == -1) mx1 = min(mx, idx2[idx]);
	a[idx] = last[val];
	ll idx3 = idx1[val];
	idx1[val] = idx; 
	idx2[idx] = val;
	s.set(a[idx], idx);
	if(mx1 == val) return;
	if(idx3 != idx) f(idx3, val + 1);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> st;
	mx = min(10, n);
	st--;
	s.init();
	for(int i = 0; i < n; i++){
		cin >> a[i];
		idx2[i] = n - a[i] + 1;
		if(n - a[i] <= mx - 2){
			s.set(a[i] + mxN, i);
			last[n - a[i] + 1] = a[i] + mxN;
			idx1[n - a[i] + 1] = i;
			a[i] += mxN; 
		}
		else s.set(a[i], i);
		if(n - a[i] == mx - 1){
			idx1[n - a[i] + 1] = i;
			last[mx] = a[i];
		}
	}
	cin >> q;
	while(q--){
		char op;
		cin >> op;
		if(op == 'F'){
			ll idx;
			cin >> idx;
			idx--;
			if(idx == st){
				cout << 0 << '\n';
				continue;
			}
			pair<ll,ll> x,x1;
			if(idx < st){
				x = s.find(idx, st);
				x1 = s.find1(x.first, st + 1, n, 0);
				if(x1.first <= x.first) cout << n - 1 - idx << '\n';
				else cout << x1.second - idx - 1 << '\n';
			}
			else{
				x = s.find(st + 1, idx + 1); 
				x1 = s.find1(x.first, 0, st, 1);
				if(x1.first <= x.first) cout << idx << '\n';
				else cout << idx - x1.second - 1 << '\n';
			}	
		}
		else{
			ll idx,val;
			mx1 = -1;
			cin >> idx >> val;
			idx--;
			f(idx, val);
//			for(int i = 0; i < n; i++) cout << a[i] << ' ';
//			cout << '\n' << "--> ";
//			for(int i = 0; i < n; i++) cout << s.find(i, i + 1).first << ' ';
//			cout << '\n';
		}
	}
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 9 ms 6696 KB Output is correct
5 Correct 99 ms 7004 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 7196 KB Output is correct
2 Correct 96 ms 7368 KB Output is correct
3 Correct 136 ms 7364 KB Output is correct
4 Correct 93 ms 7284 KB Output is correct
5 Correct 151 ms 7520 KB Output is correct
6 Correct 126 ms 7592 KB Output is correct
7 Correct 141 ms 7500 KB Output is correct
8 Correct 97 ms 7604 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2019 ms 10900 KB Time limit exceeded
2 Execution timed out 2054 ms 10896 KB Time limit exceeded
3 Execution timed out 2069 ms 10892 KB Time limit exceeded
4 Correct 1 ms 6492 KB Output is correct
5 Execution timed out 2088 ms 13028 KB Time limit exceeded
6 Execution timed out 2025 ms 13036 KB Time limit exceeded
7 Execution timed out 2025 ms 13048 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 6736 KB Output is correct
2 Correct 169 ms 6808 KB Output is correct
3 Execution timed out 2060 ms 9876 KB Time limit exceeded
4 Execution timed out 2015 ms 10228 KB Time limit exceeded
5 Correct 218 ms 6996 KB Output is correct
6 Execution timed out 2029 ms 11092 KB Time limit exceeded
7 Correct 1159 ms 7396 KB Output is correct
8 Correct 350 ms 11092 KB Output is correct
9 Execution timed out 2080 ms 13136 KB Time limit exceeded
10 Correct 711 ms 8276 KB Output is correct
11 Execution timed out 2061 ms 7628 KB Time limit exceeded
12 Execution timed out 2074 ms 12892 KB Time limit exceeded
13 Execution timed out 2019 ms 12888 KB Time limit exceeded