oj.uz

Submission #198233

# Submission time Handle Problem Language Result Execution time Memory
198233 2020-01-25T07:51:38 Z alishahali1382 Cake (CEOI14_cake) C++14
35 / 100
 2000 ms 5352 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 BS2(int id, int tl, int tr, int val){
	if (tr-tl==1) return tl;
	int mid=(tl+tr)>>1;
	if (seg[id<<1 | 1]<=val) return BS2(id<<1, tl, mid, val);
	return BS2(id<<1 | 1, mid, tr, 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';
		*/
		Add(1, 0, n+2, k, n+2, -inf);
		cout<<x-1-BS2(1, 0, n+2, mx)<<'\n';
		Add(1, 0, n+2, k, n+2, +inf);
	}
	
	
	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 3 ms 376 KB Output is correct
4 Correct 192 ms 376 KB Output is correct
5 Correct 1603 ms 780 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2053 ms 760 KB Time limit exceeded
2 Execution timed out 2081 ms 760 KB Time limit exceeded
3 Execution timed out 2009 ms 760 KB Time limit exceeded
4 Correct 217 ms 636 KB Output is correct
5 Execution timed out 2076 ms 1144 KB Time limit exceeded
6 Execution timed out 2017 ms 888 KB Time limit exceeded
7 Execution timed out 2068 ms 1016 KB Time limit exceeded
8 Correct 232 ms 888 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 3032 KB Output is correct
2 Correct 123 ms 2820 KB Output is correct
3 Correct 117 ms 2804 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 231 ms 5352 KB Output is correct
6 Correct 229 ms 5352 KB Output is correct
7 Correct 198 ms 5132 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2054 ms 628 KB Time limit exceeded
2 Execution timed out 2028 ms 736 KB Time limit exceeded
3 Execution timed out 2076 ms 1616 KB Time limit exceeded
4 Execution timed out 2070 ms 1656 KB Time limit exceeded
5 Execution timed out 2023 ms 616 KB Time limit exceeded
6 Execution timed out 2055 ms 1668 KB Time limit exceeded
7 Execution timed out 2009 ms 904 KB Time limit exceeded
8 Execution timed out 2021 ms 2420 KB Time limit exceeded
9 Execution timed out 2029 ms 4692 KB Time limit exceeded
10 Execution timed out 2065 ms 600 KB Time limit exceeded
11 Execution timed out 2041 ms 1016 KB Time limit exceeded
12 Execution timed out 2080 ms 4348 KB Time limit exceeded
13 Execution timed out 2001 ms 4796 KB Time limit exceeded