oj.uz

Submission #198232

# Submission time Handle Problem Language Result Execution time Memory
198232 2020-01-25T07:45:01 Z alishahali1382 Cake (CEOI14_cake) C++14
35 / 100
 2000 ms 5204 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;
int seg[MAXN<<2], lazy[MAXN<<2];
vector<int> Mx;

void add_lazy(int id, int val){
	seg[id]+=val;
	lazy[id]+=val;
}

void shift(int id){
	if (!lazy[id]) return ;
	add_lazy(id<<1, lazy[id]);
	add_lazy(id<<1 | 1, lazy[id]);
	lazy[id]=0;
}

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;
		return ;
	}
	shift(id);
	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]);
}

int 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];
	shift(id);
	int mid=(tl+tr)>>1;
	return max(Get(id<<1, tl, mid, l, r), Get(id<<1 | 1, mid, tr, l, r));
}

void Add(int id, int tl, int tr, int l, int r, int val){
	if (r<=tl || tr<=l) return ;
	if (l<=tl && tr<=r){
		add_lazy(id, val);
		return ;
	}
	shift(id);
	int mid=(tl+tr)>>1;
	Add(id<<1, tl, mid, l, r, val);
	Add(id<<1 | 1, mid, tr, l, r, val);
	seg[id]=max(seg[id<<1], seg[id<<1 | 1]);
}

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

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+2, 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+2, x, A[x]);
			for (int i=y-2; ~i; i--){
				A[Mx[i]]=++N;
				Set(1, 0, n+2, 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+2, x, k);
			/*
			int dwn=k, up=n+2;
			while (up-dwn>1){
				int mid=(dwn+up)>>1;
				if (Get(1, 0, n+2, k+1, mid+1)>mx) up=mid;
				else dwn=mid;
			}
			cout<<dwn-x<<'\n';
			*/
			Add(1, 0, n+2, 0, k+1, -inf);
			//debug(BS1(1, 0, n+1, mx))
			cout<<BS1(1, 0, n+2, mx)-x-1<<'\n';
			Add(1, 0, n+2, 0, k+1, +inf);
			
			continue ;
		}
		int mx=Get(1, 0, n+2, k+1, x+1);
		int dwn=0, up=k;
		while (up-dwn>1){
			int mid=(dwn+up)>>1;
			if (Get(1, 0, n+2, mid, k)>mx) dwn=mid;
			else up=mid;
		}
		cout<<x-up<<'\n';
	}
	
	
	return 0;
}
/*
5 3
5 1 2 4 3
2
F 1
F 2


5 3
5 1 2 4 3
1
F 1


*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 0 ms 376 KB Output is correct
4 Correct 195 ms 436 KB Output is correct
5 Correct 1619 ms 800 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2025 ms 636 KB Time limit exceeded
2 Execution timed out 2036 ms 632 KB Time limit exceeded
3 Execution timed out 2066 ms 632 KB Time limit exceeded
4 Correct 222 ms 628 KB Output is correct
5 Execution timed out 2079 ms 1016 KB Time limit exceeded
6 Execution timed out 2069 ms 1144 KB Time limit exceeded
7 Execution timed out 2001 ms 888 KB Time limit exceeded
8 Correct 243 ms 1020 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 2876 KB Output is correct
2 Correct 178 ms 2792 KB Output is correct
3 Correct 160 ms 2836 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 396 ms 5192 KB Output is correct
6 Correct 353 ms 5204 KB Output is correct
7 Correct 344 ms 4976 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2089 ms 516 KB Time limit exceeded
2 Execution timed out 2045 ms 700 KB Time limit exceeded
3 Execution timed out 2033 ms 1528 KB Time limit exceeded
4 Execution timed out 2076 ms 1540 KB Time limit exceeded
5 Execution timed out 2037 ms 480 KB Time limit exceeded
6 Execution timed out 2025 ms 1656 KB Time limit exceeded
7 Execution timed out 2041 ms 704 KB Time limit exceeded
8 Execution timed out 2029 ms 2304 KB Time limit exceeded
9 Execution timed out 2037 ms 4692 KB Time limit exceeded
10 Execution timed out 2041 ms 628 KB Time limit exceeded
11 Execution timed out 2015 ms 1088 KB Time limit exceeded
12 Execution timed out 2023 ms 4288 KB Time limit exceeded
13 Execution timed out 2020 ms 4772 KB Time limit exceeded