oj.uz

Submission #445739

# Submission time Handle Problem Language Result Execution time Memory
445739 2021-07-19T12:21:49 Z keta_tsimakuridze Cake (CEOI14_cake) C++14
73.3333 / 100
 1563 ms 7540 KB 
#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) 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 384 KB Output is correct
4 Correct 10 ms 376 KB Output is correct
5 Correct 27 ms 664 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 901 ms 460 KB Output is correct
2 Correct 757 ms 460 KB Output is correct
3 Correct 840 ms 460 KB Output is correct
4 Correct 791 ms 460 KB Output is correct
5 Correct 971 ms 716 KB Output is correct
6 Correct 900 ms 716 KB Output is correct
7 Correct 935 ms 716 KB Output is correct
8 Correct 917 ms 724 KB Output is correct

Subtask #3
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 2708 KB Output is correct
2 Correct 293 ms 2500 KB Output is correct
3 Correct 279 ms 2452 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Incorrect 392 ms 4552 KB Output isn't correct
6 Incorrect 395 ms 4548 KB Output isn't correct
7 Incorrect 362 ms 4292 KB Output isn't correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 416 KB Output is correct
2 Correct 107 ms 436 KB Output is correct
3 Correct 208 ms 1348 KB Output is correct
4 Correct 241 ms 1480 KB Output is correct
5 Correct 299 ms 612 KB Output is correct
6 Correct 410 ms 2380 KB Output is correct
7 Correct 439 ms 1060 KB Output is correct
8 Correct 491 ms 2116 KB Output is correct
9 Incorrect 1563 ms 5540 KB Output isn't correct
10 Correct 993 ms 1432 KB Output is correct
11 Correct 1137 ms 1984 KB Output is correct
12 Correct 1513 ms 5540 KB Output is correct
13 Incorrect 1403 ms 7540 KB Output isn't correct