oj.uz

Submission #445733

# Submission time Handle Problem Language Result Execution time Memory
445733 2021-07-19T12:17:26 Z keta_tsimakuridze Cake (CEOI14_cake) C++14
0 / 100
 1540 ms 8344 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) 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:43:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 |  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 898 ms 920 KB Output isn't correct
2 Correct 771 ms 968 KB Output is correct
3 Correct 878 ms 1060 KB Output is correct
4 Correct 804 ms 1092 KB Output is correct
5 Incorrect 1000 ms 1248 KB Output isn't correct
6 Correct 926 ms 1348 KB Output is correct
7 Correct 954 ms 1348 KB Output is correct
8 Correct 905 ms 1348 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 3396 KB Output is correct
2 Correct 283 ms 3128 KB Output is correct
3 Correct 281 ms 3068 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Incorrect 414 ms 5112 KB Output isn't correct
6 Incorrect 390 ms 5216 KB Output isn't correct
7 Incorrect 371 ms 4916 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 100 ms 756 KB Output isn't correct
2 Correct 108 ms 912 KB Output is correct
3 Correct 207 ms 2052 KB Output is correct
4 Incorrect 213 ms 1988 KB Output isn't correct
5 Incorrect 302 ms 1368 KB Output isn't correct
6 Correct 409 ms 2892 KB Output is correct
7 Correct 453 ms 1696 KB Output is correct
8 Correct 510 ms 2628 KB Output is correct
9 Incorrect 1540 ms 6328 KB Output isn't correct
10 Incorrect 976 ms 2148 KB Output isn't correct
11 Incorrect 1145 ms 2632 KB Output isn't correct
12 Correct 1442 ms 6072 KB Output is correct
13 Incorrect 1397 ms 8344 KB Output isn't correct