oj.uz

Submission #449854

# Submission time Handle Problem Language Result Execution time Memory
449854 2021-08-02T08:44:35 Z vanic Cake (CEOI14_cake) C++14
0 / 100
 314 ms 10332 KB 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn=3e5, Log=18, pot=(1<<Log);

struct tournament{
	int t[pot*2];
	void gradi(){
		for(int i=pot-1; i>0; i--){
			t[i]=max(t[i*2], t[i*2+1]);
		}
	}
	void update(int x, int val){
		t[x]=val;
		for(x>>=2; x; x>>=2){
			t[x]=max(t[x*2], t[x*2+1]);
		}
	}
	int query(int L, int D, int x, int l, int d){
		if(L>=l && D<=d){
			return t[x];
		}
		int lijeva=0, desna=0;
		if((L+D)/2>=l){
			lijeva=query(L, (L+D)/2, x*2, l, d);
		}
		if((L+D)/2+1<=d){
			desna=query((L+D)/2+1, D, x*2+1, l, d);
		}
		return max(lijeva, desna);
	}
	int nadji(int L, int D, int x, int l, int d, int val, bool s){
		if(L>=l && D<=d){
			int pos=x;
			while(pos<pot && t[pos]>val){
				if(s){
					if(t[pos*2]>val){
						pos*=2;
					}
					else{
						pos=pos*2+1;
					}
				}
				else{
					if(t[pos*2+1]>val){
						pos=pos*2+1;
					}
					else{
						pos*=2;					
					}
				}
			}
			if(t[pos]>val){
				return pos-pot;
			}
			return -1;
		}
		int p=-1;
		if(s){
			if((L+D)/2>=l){
				p=nadji(L, (L+D)/2, x*2, l, d, val, s);
				if(p!=-1){
					return p;
				}
			}
			if((L+D)/2+1<=d){
				p=nadji((L+D)/2+1, D, x*2+1, l, d, val, s);
			}
		}
		else{
			if((L+D)/2+1<=d){
				p=nadji((L+D)/2+1, D, x*2+1, l, d, val, s);
				if(p!=-1){
					return p;
				}
			}
			if((L+D)/2>=l){
				p=nadji(L, (L+D)/2, x*2, l, d, val, s);
			}
			
		}
		return p;
	}
};

tournament T;
vector < pair < int, int > > upd;


bool cmp(pair < int, int > x, pair < int, int > y){
	return x.first>y.first;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, x;
	cin >> n >> x;
	x--;
	int a;
	for(int i=0; i<n; i++){
		cin >> a;
		T.t[i+pot]=a;
		if(a>n-10){
			upd.push_back({a, i});
		}
	}
	T.gradi();
	sort(upd.begin(), upd.end(), cmp);
	int q;
	cin >> q;
	char c;
	int e, f;
	int novi, stari;
	int val1, val2;
	for(int i=0; i<q; i++){
		cin >> c >> e;
		e--;
		if(c=='F'){
			if(e==x){
				cout << 0 << '\n';
				continue;
			}
			else if(e>x){
				val1=T.query(0, pot-1, 1, x+1, e);
				if(x){
					val2=T.nadji(0, pot-1, 1, 0, x-1, val1, 0);
				}
				else{
					val2=-1;
				}
				cout << e-val2-1 << '\n';
			}
			else{
				val1=T.query(0, pot-1, 1, e, x-1);
				val2=T.nadji(0, pot-1, 1, x+1, pot-1, val1, 1);
				if(val2==-1){
					val2=n;
				}
				cout << val2-e-1 << '\n';
			}
		}
		else{
			cin >> f;
			f--;
			novi=e;
			for(int j=f; j<(int)upd.size(); j++){
				T.update(novi+pot, upd[j].first);
				stari=novi;
				novi=upd[j].second;
				upd[j].second=stari;
			}
/*			cout << "novi ";
			for(int j=0; j<n; j++){
				cout << T.query(0, pot-1, 1, j, j) << ' ';
			}
			cout << '\n';*/
		}
	}
	return 0;
}

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 154 ms 5716 KB Output isn't correct
2 Incorrect 167 ms 5716 KB Output isn't correct
3 Incorrect 163 ms 5700 KB Output isn't correct
4 Incorrect 178 ms 5712 KB Output isn't correct
5 Incorrect 159 ms 6028 KB Output isn't correct
6 Incorrect 166 ms 6400 KB Output isn't correct
7 Incorrect 174 ms 6272 KB Output isn't correct
8 Incorrect 176 ms 6536 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 3796 KB Output isn't correct
2 Incorrect 75 ms 3708 KB Output isn't correct
3 Incorrect 63 ms 3428 KB Output isn't correct
4 Incorrect 1 ms 1228 KB Output isn't correct
5 Incorrect 100 ms 5336 KB Output isn't correct
6 Incorrect 88 ms 5356 KB Output isn't correct
7 Incorrect 65 ms 5216 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 1844 KB Output isn't correct
2 Incorrect 26 ms 1872 KB Output isn't correct
3 Incorrect 47 ms 2668 KB Output isn't correct
4 Incorrect 40 ms 2656 KB Output isn't correct
5 Incorrect 64 ms 2704 KB Output isn't correct
6 Incorrect 91 ms 3684 KB Output isn't correct
7 Incorrect 93 ms 3384 KB Output isn't correct
8 Incorrect 82 ms 4140 KB Output isn't correct
9 Incorrect 314 ms 10332 KB Output isn't correct
10 Incorrect 234 ms 6224 KB Output isn't correct
11 Incorrect 228 ms 7040 KB Output isn't correct
12 Incorrect 270 ms 9828 KB Output isn't correct
13 Incorrect 267 ms 10280 KB Output isn't correct