oj.uz

Submission #445738

# Submission time Handle Problem Language Result Execution time Memory
445738 2021-07-19T12:20:48 Z keta_tsimakuridze Cake (CEOI14_cake) C++14
0 / 100
 1490 ms 7728 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[i] = mx[i+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
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 890 ms 548 KB Output isn't correct
2 Correct 707 ms 584 KB Output is correct
3 Correct 827 ms 460 KB Output is correct
4 Correct 753 ms 588 KB Output is correct
5 Incorrect 904 ms 716 KB Output isn't correct
6 Correct 842 ms 716 KB Output is correct
7 Correct 914 ms 716 KB Output is correct
8 Correct 855 ms 716 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 2624 KB Output is correct
2 Correct 282 ms 2456 KB Output is correct
3 Correct 280 ms 2488 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Incorrect 386 ms 4452 KB Output isn't correct
6 Incorrect 424 ms 4520 KB Output isn't correct
7 Incorrect 361 ms 4272 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 488 KB Output isn't correct
2 Correct 103 ms 432 KB Output is correct
3 Correct 204 ms 1368 KB Output is correct
4 Correct 205 ms 1348 KB Output is correct
5 Incorrect 294 ms 616 KB Output isn't correct
6 Correct 403 ms 2172 KB Output is correct
7 Correct 432 ms 900 KB Output is correct
8 Correct 490 ms 2168 KB Output is correct
9 Incorrect 1490 ms 5676 KB Output isn't correct
10 Incorrect 1002 ms 1504 KB Output isn't correct
11 Correct 1213 ms 2128 KB Output is correct
12 Correct 1451 ms 5712 KB Output is correct
13 Incorrect 1410 ms 7728 KB Output isn't correct