oj.uz

Submission #198234

# Submission time Handle Problem Language Result Execution time Memory
198234 2020-01-25T07:56:46 Z alishahali1382 Cake (CEOI14_cake) C++14
0 / 100
 241 ms 9068 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());
			
			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


*/

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 1144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 8 ms 1144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 6 ms 1144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 223 ms 680 KB Output isn't correct
5 Runtime error 14 ms 1784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 14 ms 1656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 14 ms 1752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Incorrect 241 ms 984 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 4484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 57 ms 4596 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 56 ms 4596 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 2 ms 380 KB Output isn't correct
5 Runtime error 139 ms 9068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 139 ms 8944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Incorrect 129 ms 4468 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 5 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 26 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 28 ms 2680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 4 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 34 ms 2932 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 7 ms 1144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 54 ms 4548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 138 ms 8944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 4 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 12 ms 1656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 112 ms 8272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 144 ms 9036 KB Execution killed with signal 11 (could be triggered by violating memory limits)