oj.uz

답안 #70934

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
70934 2018-08-23T19:32:00 Z spencercompton 케이크 (CEOI14_cake) C++17
0 / 100
 2000 ms 83408 KB 
#include <bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//O(N + (10 + log N)Q)
	//no treap bs :)
	int n, s;
	cin >> n >> s;
	s--;
	int bigs = min(n,10);
	bool isbig[n];
	int pos[n];
	int aux = 0;
	int top[bigs];
	for(int i = 0; i<n; i++){
		cin >> pos[i];
		pos[i] = n-pos[i];
		isbig[i] = pos[i]<bigs;
		top[pos[i]] = i;
	}
	vector<int> l;
	vector<int> r;
	for(int i = s-1; i>=0; i--){
		if(l.size()==0 || pos[l.back()]>pos[i]){
			l.push_back(i);
		}
	}
	for(int i = s+1; i<n; i++){
		if(r.size()==0 || pos[r.back()]>pos[i]){
			r.push_back(i);
		}
	}
	int q;
	cin >> q;
	for(int z = 0; z<q; z++){
		string str;
		cin >> str;
		if(str=="E"){
			int ind, loc;
			cin >> ind >> loc;
			ind--;
			loc--;
			vector<int> nex;
			aux++;
			for(int i = 0; i<loc; i++){
				nex.push_back(top[i]);
			}
			nex.push_back(ind);
			for(int i = loc; i<bigs; i++){
				if(top[i]==ind){
					continue;
				}
				nex.push_back(top[i]);
			}
			for(int i = 0; i<bigs; i++){
				isbig[nex[i]] = true;
				pos[nex[i]] = i;
				top[i] = nex[i];
			}
			if(nex.size()>bigs){
				isbig[nex[bigs]] = false;
				pos[nex[bigs]] = -aux + bigs;
			}
			nex.clear();

			if(ind<s){
				vector<int> el;
				while(l.size()>0){
					int cur = l.back();
					if(isbig[cur] && pos[cur]<=loc){
						el.push_back(cur);
						l.pop_back();
					}
					else{
						break;
					}
				}
				if(el.size()==0 || el.back()<ind){
					el.push_back(ind);
					while(l.size()>0 && l.back()<ind){
						l.pop_back();
					}
				}
				while(el.size()>0){
					l.push_back(el.back());
					el.pop_back();
				}
			}
			else if(ind>s){
				vector<int> er;
				while(r.size()>0){
					int cur = r.back();
					if(isbig[cur] && pos[cur]<=loc){
						er.push_back(cur);
						r.pop_back();
					}
					else{
						break;
					}
				}
				if(er.size()==0 || er.back()>ind){
					er.push_back(ind);
					while(r.size()>0 && r.back()>ind){
						r.pop_back();
					}
				}
				while(er.size()>0){
					r.push_back(er.back());
					er.pop_back();
				}
			}
		}
		if(str=="F"){
			//get answer for this
			int ind;
			cin >> ind;
			ind--;
			int ret = 0;
			if(ind<s){
				ret += s-ind;
				int lo = 0;
				int hi = l.size()-1;
				while(lo<hi){
					int mid = (lo+hi+1)/2;
					if(l[mid]>=ind){
						lo = mid;
					}
					else{
						hi = mid-1;
					}
				}
				int bar = pos[l[lo]];
				if(!isbig[l[lo]]){
					bar = pos[l[lo]] + aux;
				}
				if(r.size()>0){
					int val = pos[r.back()];
					if(!isbig[r.back()]){
						val = pos[r.back()] + aux;
					}
					if(val>=bar){
						ret += n-s-1;
					}
					else{
						int lo = 0;
						int hi = r.size()-1;
						while(lo<hi){
							int mid = (lo+hi)/2;
							val = pos[r[mid]];
							if(!isbig[r[mid]]){
								val = pos[r[mid]] + aux;
							}
							if(val>=bar){
								lo = mid+1;
							}
							else{
								hi = mid;
							}
						}
						ret += r[lo]-s-1;
					}
				}
			}
			else if(ind>s){
				ret += ind-s;

				int lo = 0;
				int hi = r.size()-1;
				while(lo<hi){
					int mid = (lo+hi+1)/2;
					if(r[mid]>=ind){
						lo = mid;
					}
					else{
						hi = mid-1;
					}
				}
				int bar = pos[r[lo]];
				if(!isbig[r[lo]]){
					bar = pos[r[lo]] + aux;
				}
				if(l.size()>0){
					int val = pos[l.back()];
					if(!isbig[l.back()]){
						val = pos[l.back()] + aux;
					}
					if(val>=bar){
						ret += s;
					}
					else{
						int lo = 0;
						int hi = l.size()-1;
						while(lo<hi){
							int mid = (lo+hi)/2;
							val = pos[l[mid]];
							if(!isbig[l[mid]]){
								val = pos[l[mid]] + aux;
							}
							if(val>=bar){
								lo = mid+1;
							}
							else{
								hi = mid;
							}
						}
						ret += s-l[lo]-1;
					}
				}
			}
			cout << ret << endl;
		}
	}
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:62:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(nex.size()>bigs){
       ~~~~~~~~~~^~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 385 ms 4900 KB Output isn't correct
2 Execution timed out 2073 ms 8308 KB Time limit exceeded
3 Incorrect 513 ms 12564 KB Output isn't correct
4 Correct 419 ms 17088 KB Output is correct
5 Incorrect 446 ms 21816 KB Output isn't correct
6 Execution timed out 2069 ms 23608 KB Time limit exceeded
7 Incorrect 489 ms 28160 KB Output isn't correct
8 Correct 389 ms 33176 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 231 ms 35384 KB Output isn't correct
2 Incorrect 218 ms 36720 KB Output isn't correct
3 Incorrect 207 ms 38056 KB Output isn't correct
4 Correct 2 ms 38056 KB Output is correct
5 Incorrect 224 ms 41360 KB Output isn't correct
6 Incorrect 264 ms 43860 KB Output isn't correct
7 Correct 264 ms 46028 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 79 ms 46028 KB Output isn't correct
2 Incorrect 78 ms 46028 KB Output isn't correct
3 Incorrect 161 ms 46792 KB Output isn't correct
4 Incorrect 131 ms 47552 KB Output isn't correct
5 Incorrect 213 ms 48724 KB Output isn't correct
6 Incorrect 259 ms 50576 KB Output isn't correct
7 Incorrect 299 ms 52048 KB Output isn't correct
8 Incorrect 210 ms 54524 KB Output isn't correct
9 Incorrect 825 ms 63160 KB Output isn't correct
10 Incorrect 685 ms 65292 KB Output isn't correct
11 Incorrect 738 ms 69720 KB Output isn't correct
12 Incorrect 783 ms 76872 KB Output isn't correct
13 Incorrect 869 ms 83408 KB Output isn't correct