oj.uz

Submission #449893

# Submission time Handle Problem Language Result Execution time Memory
449893 2021-08-02T09:08:54 Z vanic Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 72076 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 Execution timed out 2081 ms 55808 KB Time limit exceeded
2 Execution timed out 2094 ms 53996 KB Time limit exceeded
3 Execution timed out 2098 ms 55492 KB Time limit exceeded
4 Execution timed out 2091 ms 55408 KB Time limit exceeded
5 Execution timed out 2043 ms 52764 KB Time limit exceeded
6 Execution timed out 2068 ms 63812 KB Time limit exceeded
7 Execution timed out 2083 ms 57452 KB Time limit exceeded
8 Execution timed out 2091 ms 59588 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1996 ms 58372 KB Output isn't correct
2 Incorrect 1703 ms 53312 KB Output isn't correct
3 Incorrect 1646 ms 52164 KB Output isn't correct
4 Incorrect 1 ms 1228 KB Output isn't correct
5 Execution timed out 2075 ms 70980 KB Time limit exceeded
6 Execution timed out 2071 ms 68616 KB Time limit exceeded
7 Execution timed out 2071 ms 72076 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2079 ms 53856 KB Time limit exceeded
2 Execution timed out 2083 ms 55068 KB Time limit exceeded
3 Execution timed out 2048 ms 60036 KB Time limit exceeded
4 Execution timed out 2074 ms 58204 KB Time limit exceeded
5 Execution timed out 2083 ms 52524 KB Time limit exceeded
6 Execution timed out 2054 ms 61184 KB Time limit exceeded
7 Execution timed out 2083 ms 56696 KB Time limit exceeded
8 Execution timed out 2094 ms 63628 KB Time limit exceeded
9 Execution timed out 2083 ms 68336 KB Time limit exceeded
10 Execution timed out 2090 ms 54548 KB Time limit exceeded
11 Execution timed out 2094 ms 59320 KB Time limit exceeded
12 Execution timed out 2081 ms 68172 KB Time limit exceeded
13 Execution timed out 2045 ms 71104 KB Time limit exceeded