oj.uz

Submission #445728

# Submission time Handle Problem Language Result Execution time Memory
445728 2021-07-19T12:13:35 Z keta_tsimakuridze Cake (CEOI14_cake) C++14
0 / 100
 1492 ms 13964 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)  {
		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

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

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 906 ms 4840 KB Output isn't correct
2 Correct 782 ms 4980 KB Output is correct
3 Correct 861 ms 4976 KB Output is correct
4 Correct 832 ms 4976 KB Output is correct
5 Incorrect 977 ms 5476 KB Output isn't correct
6 Correct 893 ms 5872 KB Output is correct
7 Correct 972 ms 5736 KB Output is correct
8 Correct 915 ms 5960 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 4036 KB Output is correct
2 Correct 279 ms 3808 KB Output is correct
3 Correct 278 ms 3936 KB Output is correct
4 Incorrect 1 ms 304 KB Output isn't correct
5 Incorrect 388 ms 6908 KB Output isn't correct
6 Incorrect 384 ms 7140 KB Output isn't correct
7 Incorrect 377 ms 6720 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 110 ms 836 KB Output isn't correct
2 Correct 104 ms 812 KB Output is correct
3 Correct 204 ms 2224 KB Output is correct
4 Incorrect 202 ms 2456 KB Output isn't correct
5 Incorrect 288 ms 1756 KB Output isn't correct
6 Correct 402 ms 3948 KB Output is correct
7 Correct 426 ms 2572 KB Output is correct
8 Correct 509 ms 4548 KB Output is correct
9 Incorrect 1492 ms 11860 KB Output isn't correct
10 Incorrect 1006 ms 5028 KB Output isn't correct
11 Incorrect 1127 ms 6436 KB Output isn't correct
12 Correct 1412 ms 11432 KB Output is correct
13 Incorrect 1384 ms 13964 KB Output isn't correct