Submission #70945

#	Time	Username	Problem	Language	Result	Execution time	Memory
70945		spencercompton	Cake (CEOI14_cake)	C++17	0 / 100	711 ms	10780 KiB

cake

#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;
		if(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){
			    assert(nex.size()==bigs+1);
				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]<=pos[ind]){
						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]<=pos[ind]){
						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 (stderr)

cake.cpp: In function 'int main()':
cake.cpp:64:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(nex.size()>bigs){
       ~~~~~~~~~~^~~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from cake.cpp:1:
cake.cpp:65:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        assert(nex.size()==bigs+1);
               ~~~~~~~~~~^~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50