oj.uz

Submission #70947

# Submission time Handle Problem Language Result Execution time Memory
70947 2018-08-23T20:03:57 Z spencercompton Cake (CEOI14_cake) C++17
100 / 100
 766 ms 3892 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;
		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

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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 3 ms 600 KB Output is correct
4 Correct 9 ms 828 KB Output is correct
5 Correct 19 ms 1032 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 1032 KB Output is correct
2 Correct 331 ms 1032 KB Output is correct
3 Correct 371 ms 1032 KB Output is correct
4 Correct 298 ms 1032 KB Output is correct
5 Correct 371 ms 1032 KB Output is correct
6 Correct 410 ms 1032 KB Output is correct
7 Correct 364 ms 1032 KB Output is correct
8 Correct 354 ms 1144 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 1928 KB Output is correct
2 Correct 192 ms 1928 KB Output is correct
3 Correct 187 ms 1928 KB Output is correct
4 Correct 2 ms 1928 KB Output is correct
5 Correct 236 ms 2740 KB Output is correct
6 Correct 215 ms 2808 KB Output is correct
7 Correct 220 ms 2808 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 2808 KB Output is correct
2 Correct 72 ms 2808 KB Output is correct
3 Correct 122 ms 2808 KB Output is correct
4 Correct 108 ms 2808 KB Output is correct
5 Correct 218 ms 2808 KB Output is correct
6 Correct 223 ms 2808 KB Output is correct
7 Correct 246 ms 2808 KB Output is correct
8 Correct 182 ms 2808 KB Output is correct
9 Correct 766 ms 3808 KB Output is correct
10 Correct 673 ms 3808 KB Output is correct
11 Correct 628 ms 3808 KB Output is correct
12 Correct 688 ms 3808 KB Output is correct
13 Correct 672 ms 3892 KB Output is correct