oj.uz

Submission #449882

# Submission time Handle Problem Language Result Execution time Memory
449882 2021-08-02T08:57:42 Z vanic Cake (CEOI14_cake) C++14
0 / 100
 287 ms 3964 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;
	bool p;
	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;
			p=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;
				if(novi==e){
					p=0;
					break;
				}
			}
			if(p){
				T.update(novi+pot, tren);
				tren++;
			}
/*			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 127 ms 1360 KB Output isn't correct
2 Incorrect 108 ms 1360 KB Output isn't correct
3 Incorrect 126 ms 1364 KB Output isn't correct
4 Incorrect 121 ms 1368 KB Output isn't correct
5 Incorrect 142 ms 1420 KB Output isn't correct
6 Incorrect 123 ms 1356 KB Output isn't correct
7 Incorrect 130 ms 1356 KB Output isn't correct
8 Incorrect 113 ms 1356 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 2192 KB Output isn't correct
2 Incorrect 65 ms 2176 KB Output isn't correct
3 Incorrect 56 ms 2104 KB Output isn't correct
4 Correct 1 ms 1228 KB Output is correct
5 Incorrect 96 ms 2892 KB Output isn't correct
6 Incorrect 95 ms 2884 KB Output isn't correct
7 Incorrect 65 ms 2844 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 1388 KB Output isn't correct
2 Incorrect 25 ms 1484 KB Output isn't correct
3 Incorrect 43 ms 1684 KB Output isn't correct
4 Incorrect 41 ms 1672 KB Output isn't correct
5 Incorrect 65 ms 1604 KB Output isn't correct
6 Incorrect 101 ms 1984 KB Output isn't correct
7 Incorrect 112 ms 1792 KB Output isn't correct
8 Incorrect 67 ms 1728 KB Output isn't correct
9 Incorrect 287 ms 3936 KB Output isn't correct
10 Incorrect 224 ms 2520 KB Output isn't correct
11 Incorrect 236 ms 2692 KB Output isn't correct
12 Incorrect 283 ms 3676 KB Output isn't correct
13 Incorrect 263 ms 3964 KB Output isn't correct