oj.uz

Submission #198235

# Submission time Handle Problem Language Result Execution time Memory
198235 2020-01-25T08:00:34 Z alishahali1382 Cake (CEOI14_cake) C++14
100 / 100
 861 ms 10712 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));
	
	//debugv(Mx)
	
	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());
			while (Mx.size()>10) Mx.pop_back();
			
			assert(Mx.size()<=10);
			
			// I hope thats just it!
			
			continue ;
		}
		//continue ;
		cin>>x;
		if (x==k){
			cout<<"0\n";
			continue ;
		}
		if (x<k){
			int mx=Get(1, 0, n+2, x, k);
			Add(1, 0, n+2, 0, k+1, -inf);
			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);
		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


15 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
5
E 14 1
E 13 1
E 15 1
E 12 1
E 11 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 2 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 16 ms 632 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 4700 KB Output is correct
2 Correct 300 ms 4500 KB Output is correct
3 Correct 319 ms 4732 KB Output is correct
4 Correct 222 ms 700 KB Output is correct
5 Correct 467 ms 5228 KB Output is correct
6 Correct 395 ms 5484 KB Output is correct
7 Correct 353 ms 5244 KB Output is correct
8 Correct 236 ms 888 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 2992 KB Output is correct
2 Correct 123 ms 2804 KB Output is correct
3 Correct 118 ms 2676 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 228 ms 5200 KB Output is correct
6 Correct 231 ms 5440 KB Output is correct
7 Correct 204 ms 5112 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 632 KB Output is correct
2 Correct 42 ms 732 KB Output is correct
3 Correct 93 ms 1992 KB Output is correct
4 Correct 115 ms 1908 KB Output is correct
5 Correct 126 ms 1492 KB Output is correct
6 Correct 169 ms 3060 KB Output is correct
7 Correct 142 ms 2512 KB Output is correct
8 Correct 213 ms 3956 KB Output is correct
9 Correct 861 ms 10628 KB Output is correct
10 Correct 417 ms 4868 KB Output is correct
11 Correct 538 ms 6260 KB Output is correct
12 Correct 819 ms 10248 KB Output is correct
13 Correct 777 ms 10712 KB Output is correct