oj.uz

Submission #445740

# Submission time Handle Problem Language Result Execution time Memory
445740 2021-07-19T12:22:44 Z keta_tsimakuridze Cake (CEOI14_cake) C++14
100 / 100
 1489 ms 8076 KB 
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=25e4+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) return 0;
	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) return n-k+1;
	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=10;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<<"\n";
			}
			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<<"\n";				
			}
			else cout<<0<<"\n";
		}
		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)  {
					for(int j=i;j<=10;j++) {
						mx[j] = mx[j+1];
					}
					break;
				}
			}
			for(int i=10;i>e;i--){
				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

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 10 ms 348 KB Output is correct
5 Correct 26 ms 708 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 876 ms 460 KB Output is correct
2 Correct 728 ms 460 KB Output is correct
3 Correct 828 ms 460 KB Output is correct
4 Correct 781 ms 460 KB Output is correct
5 Correct 972 ms 716 KB Output is correct
6 Correct 876 ms 716 KB Output is correct
7 Correct 922 ms 716 KB Output is correct
8 Correct 941 ms 716 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 2628 KB Output is correct
2 Correct 284 ms 2636 KB Output is correct
3 Correct 283 ms 2500 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 421 ms 4984 KB Output is correct
6 Correct 382 ms 5024 KB Output is correct
7 Correct 367 ms 4712 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 508 KB Output is correct
2 Correct 105 ms 564 KB Output is correct
3 Correct 245 ms 1412 KB Output is correct
4 Correct 206 ms 1476 KB Output is correct
5 Correct 299 ms 620 KB Output is correct
6 Correct 420 ms 2296 KB Output is correct
7 Correct 437 ms 1112 KB Output is correct
8 Correct 509 ms 2116 KB Output is correct
9 Correct 1489 ms 5916 KB Output is correct
10 Correct 1020 ms 1600 KB Output is correct
11 Correct 1147 ms 2124 KB Output is correct
12 Correct 1467 ms 5792 KB Output is correct
13 Correct 1392 ms 8076 KB Output is correct