oj.uz

Submission #198224

# Submission time Handle Problem Language Result Execution time Memory
198224 2020-01-25T07:19:22 Z alishahali1382 Cake (CEOI14_cake) C++14
35 / 100
 2000 ms 9772 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 250010, LOG=20;

int n, m, k, u, v, x, y, t, a, b, ans;
int A[MAXN], N;
pii seg[MAXN<<2];
vector<int> Mx;

void Set(int id, int tl, int tr, int pos, int val){
	if (pos<tl || tr<=pos) return ;
	if (tr-tl==1){
		seg[id]={val, pos};
		return ;
	}
	int mid=(tl+tr)>>1;
	Set(id<<1, tl, mid, pos, val);
	Set(id<<1 | 1, mid, tr, pos, val);
	seg[id]=max(seg[id<<1], seg[id<<1 | 1]);
}

pii Get(int id, int tl, int tr, int l, int r){
	if (r<=tl || tr<=l) return seg[0];
	if (l<=tl && tr<=r) return seg[id];
	int mid=(tl+tr)>>1;
	return max(Get(id<<1, tl, mid, l, r), Get(id<<1 | 1, mid, tr, l, r));
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>k;
	for (int i=1; i<=n; i++) cin>>A[i], Mx.pb(i);
	//A[k]=0; // maybe bug
	A[0]=inf;
	A[n+1]=inf;
	N=n;
	
	for (int i=0; i<=n+1; i++) Set(1, 0, n+1, i, A[i]);
	
	sort(all(Mx), [](int i, int j){
		return A[i]>A[j];
	});
	Mx.resize(min(n, 10));
	
	cin>>m;
	char typ;
	while (m--){
		cin>>typ;
		if (typ=='E'){
			cin>>x>>y;
			//if (x==k) continue ; // maybe bug
			A[x]=++N;
			Set(1, 0, n+1, x, A[x]);
			for (int i=y-2; ~i; i--){
				A[Mx[i]]=++N;
				Set(1, 0, n+1, Mx[i], A[Mx[i]]);
			}
			
			Mx.pb(x);
			sort(all(Mx), [](int i, int j){
				return A[i]>A[j];
			});
			Mx.resize(unique(all(Mx))-Mx.begin());
			
			// I hope thats just it!
			
			continue ;
		}
		cin>>x;
		if (x==k){
			cout<<"0\n";
			continue ;
		}
		if (x<k){
			int mx=Get(1, 0, n+1, x, k).first;
			int dwn=k, up=n+1;
			while (up-dwn>1){
				int mid=(dwn+up)>>1;
				if (Get(1, 0, n+1, k+1, mid+1).first>mx) up=mid;
				else dwn=mid;
			}
			cout<<dwn-x<<'\n';
			
			continue ;
		}
		int mx=Get(1, 0, n+1, k+1, x+1).first;
		int dwn=0, up=k;
		while (up-dwn>1){
			int mid=(dwn+up)>>1;
			if (Get(1, 0, n+1, mid, k).first>mx) dwn=mid;
			else up=mid;
		}
		cout<<x-up<<'\n';
	}
	
	
	return 0;
}
/*
5 3
5 1 2 4 3
2
F 1
F 2


*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 195 ms 376 KB Output is correct
5 Correct 1644 ms 996 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2047 ms 1040 KB Time limit exceeded
2 Execution timed out 2020 ms 1400 KB Time limit exceeded
3 Execution timed out 2015 ms 1032 KB Time limit exceeded
4 Correct 223 ms 5256 KB Output is correct
5 Execution timed out 2005 ms 1528 KB Time limit exceeded
6 Execution timed out 2067 ms 1600 KB Time limit exceeded
7 Execution timed out 2032 ms 1608 KB Time limit exceeded
8 Correct 238 ms 6264 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 5352 KB Output is correct
2 Correct 503 ms 5288 KB Output is correct
3 Correct 490 ms 4976 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 520 ms 9772 KB Output is correct
6 Correct 696 ms 9628 KB Output is correct
7 Correct 599 ms 9728 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2037 ms 1028 KB Time limit exceeded
2 Execution timed out 2037 ms 888 KB Time limit exceeded
3 Execution timed out 2007 ms 2616 KB Time limit exceeded
4 Execution timed out 2025 ms 2580 KB Time limit exceeded
5 Execution timed out 2033 ms 916 KB Time limit exceeded
6 Execution timed out 2023 ms 2844 KB Time limit exceeded
7 Execution timed out 2060 ms 1284 KB Time limit exceeded
8 Execution timed out 2033 ms 4228 KB Time limit exceeded
9 Execution timed out 2097 ms 8600 KB Time limit exceeded
10 Execution timed out 2029 ms 1016 KB Time limit exceeded
11 Execution timed out 2062 ms 1688 KB Time limit exceeded
12 Execution timed out 2041 ms 7888 KB Time limit exceeded
13 Execution timed out 2049 ms 8816 KB Time limit exceeded