oj.uz

Submission #449919

# Submission time Handle Problem Language Result Execution time Memory
449919 2021-08-02T09:36:42 Z vanic Cake (CEOI14_cake) C++14
100 / 100
 369 ms 4680 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>>=1; x; x>>=1){
			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){
//			cout << "querij " << L << ' ' << D << ' ' <<  t[x] << endl;
			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<< val1 << ' ' << val2 << endl;
				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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB Output is correct
2 Correct 2 ms 1228 KB Output is correct
3 Correct 2 ms 1228 KB Output is correct
4 Correct 4 ms 1356 KB Output is correct
5 Correct 8 ms 1508 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 1936 KB Output is correct
2 Correct 153 ms 1844 KB Output is correct
3 Correct 204 ms 1740 KB Output is correct
4 Correct 148 ms 1844 KB Output is correct
5 Correct 201 ms 1868 KB Output is correct
6 Correct 205 ms 1880 KB Output is correct
7 Correct 212 ms 1888 KB Output is correct
8 Correct 158 ms 1884 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 2744 KB Output is correct
2 Correct 64 ms 2528 KB Output is correct
3 Correct 57 ms 2496 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 100 ms 3408 KB Output is correct
6 Correct 86 ms 3384 KB Output is correct
7 Correct 70 ms 3148 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1724 KB Output is correct
2 Correct 35 ms 1772 KB Output is correct
3 Correct 61 ms 2140 KB Output is correct
4 Correct 54 ms 2200 KB Output is correct
5 Correct 84 ms 2172 KB Output is correct
6 Correct 111 ms 2512 KB Output is correct
7 Correct 134 ms 2296 KB Output is correct
8 Correct 109 ms 2240 KB Output is correct
9 Correct 369 ms 4680 KB Output is correct
10 Correct 288 ms 3032 KB Output is correct
11 Correct 309 ms 3188 KB Output is correct
12 Correct 369 ms 4216 KB Output is correct
13 Correct 313 ms 4416 KB Output is correct