oj.uz

Submission #449894

# Submission time Handle Problem Language Result Execution time Memory
449894 2021-08-02T09:09:28 Z vanic Cake (CEOI14_cake) C++14
0 / 100
 339 ms 4316 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;
		if(a>n-10){
			a=(a-n+10)*1e6;
			upd.push_back({a, i});
		}
		T.t[i+pot]=a;
//		cout << a << ' ';
	}
//	cout << '\n';
	T.gradi();
	sort(upd.begin(), upd.end(), cmp);
	int q;
	cin >> q;
	char c;
	int e, f;
	int novi, stari;
	int val1, val2;
	int tren=n+1;
	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;
			int ind=-1;
			for(int j=0; j<(int)upd.size(); j++){
				if(upd[j].second==e){
					ind=j;
					break;
				}
			}
			if(ind==-1){
				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;
				}
				T.update(novi+pot, tren);
				tren++;
			}
			else if(ind>f){
				for(int j=f; j<=ind; j++){
					T.update(novi+pot, upd[j].first);
					stari=novi;
					novi=upd[j].second;
					upd[j].second=stari;
				}
			}
			else if(ind<f){
				for(int j=f; j>=ind; 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 << endl;*/
		}
	}
	return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 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 156 ms 1388 KB Output isn't correct
2 Incorrect 110 ms 1356 KB Output isn't correct
3 Incorrect 158 ms 1400 KB Output isn't correct
4 Incorrect 109 ms 1396 KB Output isn't correct
5 Incorrect 135 ms 1420 KB Output isn't correct
6 Incorrect 130 ms 1416 KB Output isn't correct
7 Incorrect 136 ms 1420 KB Output isn't correct
8 Incorrect 131 ms 1356 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 2188 KB Output isn't correct
2 Incorrect 64 ms 2132 KB Output isn't correct
3 Incorrect 80 ms 2148 KB Output isn't correct
4 Correct 1 ms 1228 KB Output is correct
5 Incorrect 144 ms 2932 KB Output isn't correct
6 Incorrect 105 ms 2864 KB Output isn't correct
7 Incorrect 93 ms 2872 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 1464 KB Output isn't correct
2 Incorrect 27 ms 1412 KB Output isn't correct
3 Incorrect 45 ms 1712 KB Output isn't correct
4 Incorrect 40 ms 1740 KB Output isn't correct
5 Incorrect 89 ms 1936 KB Output isn't correct
6 Incorrect 86 ms 2180 KB Output isn't correct
7 Incorrect 97 ms 2056 KB Output isn't correct
8 Incorrect 68 ms 2008 KB Output isn't correct
9 Incorrect 339 ms 4316 KB Output isn't correct
10 Incorrect 268 ms 2768 KB Output isn't correct
11 Incorrect 235 ms 3036 KB Output isn't correct
12 Incorrect 294 ms 4044 KB Output isn't correct
13 Incorrect 275 ms 4212 KB Output isn't correct