Submission #445728

#	Time	Username	Problem	Language	Result	Execution time	Memory
445728		keta_tsimakuridze	Cake (CEOI14_cake)	C++14	0 / 100	1492 ms	13964 KiB

cake

#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t,tree[4*N][2],a[N],ind[N],mx[N],n,k;
void update(int u,int ind,int l,int r,int val,int t) {
	if(l==r) {
		tree[u][t] = val;
		return;
	}
	int mid = (l+r)/2;
	if(ind <= mid) update(2*u,ind,l,mid,val,t);
	else update(2*u+1,ind,mid+1,r,val,t);
	tree[u][t] = max(tree[2*u][t],tree[2*u+1][t]);
}
int getans(int u,int start,int end,int l,int r,int t){
	if(l>end || r<start) return 0;
	if(start<=l && r<=end) return tree[u][t];
	int mid = (l+r)/2;
	return max(getans(2*u,start,end,l,mid,t),getans(2*u+1,start,end,mid+1,r,t));
}
int get_mx(int u,int l,int r,int val){
	if(l==r)  {
		if(a[l] < val) return 0;
		return l;
	}
	int mid = (l+r)/2;
	if(tree[2*u+1][0] >= val) return get_mx(2*u+1,mid+1,r,val);
	return get_mx(2*u,l,mid,val);
}
int get_mn(int u,int l,int r,int val){
	if(l==r) {
		if(a[l + k] < val) return n - k + 1;
		return l;
	}
	int mid = (l+r)/2;
	if(tree[2*u][1] >= val) return get_mn(2*u,l,mid,val);
	return get_mn(2*u+1,mid+1,r,val);	
}
 main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ind[a[i]] = i;
		if(i < k) {
			update(1,i,1,k-1,a[i],0);
		}
		else if(i > k)update(1,i-k,1,n-k,a[i],1);
		for(int j=1;j<=10;j++) {
			if(a[mx[j]]< a[i]) {
				for(int k=9;k>=j;k--) {
					swap(mx[k],mx[k+1]);
				}
				mx[j] = i;
				break;
			}
		}
	
	}
	int q;
	cin>>q;
	int cur = n;
	while(q--) {
		char c;
		cin>>c;
		if(c=='F') {
			int b;
			cin >> b;
			if(b > k) {
				int mx = getans(1,1,b-k,1,n-k,1);
				cout<<  b -  get_mx(1,1,k-1,mx) - 1<<" ";
			}
			else if(b<k){
				
				int mx = getans(1,b,k-1,1,k-1,0);
				cout<< -b +  get_mn(1,1,n-k,mx) + k-  1<<" ";				
			}
			else cout<<0<<" ";
		}
		else  {
			int idx,e;
			cin >> idx >> e;
			for(int i=10;i>=e;i--) {
				swap(mx[i],mx[i+1]);
			}
			for(int i=10;i>e;i--) {
				if(mx[i] == idx) mx[i] = mx[11];
				if(mx[i] < k) update(1,mx[i],1,k-1,a[mx[i]],0);
				if(mx[i] > k) update(1,mx[i]-k,1,n-k,a[mx[i]],1);
			}
			mx[e] = idx;
			for(int i=e;i>=1;i--) {
				a[mx[i]] = ++cur;
				if(mx[i] < k) update(1,mx[i],1,k-1,cur,0);
				if(mx[i] > k) update(1,mx[i]-k,1,n-k,cur,1);
			}
		
		}
	}
	
}

Compilation message (stderr)

cake.cpp:41:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   41 |  main(){
      |  ^~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50