oj.uz

Submission #70945

# Submission time Handle Problem Language Result Execution time Memory
70945 2018-08-23T19:55:19 Z spencercompton Cake (CEOI14_cake) C++17
0 / 100
 711 ms 10780 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 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 367 ms 2672 KB Output isn't correct
2 Correct 326 ms 4056 KB Output is correct
3 Incorrect 370 ms 4224 KB Output isn't correct
4 Correct 317 ms 4224 KB Output is correct
5 Incorrect 416 ms 4328 KB Output isn't correct
6 Incorrect 353 ms 8064 KB Output isn't correct
7 Incorrect 352 ms 8064 KB Output isn't correct
8 Correct 310 ms 8064 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 182 ms 8872 KB Output isn't correct
2 Incorrect 194 ms 8904 KB Output isn't correct
3 Incorrect 205 ms 8904 KB Output isn't correct
4 Correct 3 ms 8904 KB Output is correct
5 Incorrect 218 ms 9784 KB Output isn't correct
6 Incorrect 238 ms 9784 KB Output isn't correct
7 Correct 224 ms 9784 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 9784 KB Output isn't correct
2 Incorrect 61 ms 9784 KB Output isn't correct
3 Incorrect 101 ms 9784 KB Output isn't correct
4 Incorrect 107 ms 9784 KB Output isn't correct
5 Incorrect 178 ms 9784 KB Output isn't correct
6 Incorrect 206 ms 9784 KB Output isn't correct
7 Incorrect 240 ms 9784 KB Output isn't correct
8 Incorrect 182 ms 9784 KB Output isn't correct
9 Incorrect 711 ms 10736 KB Output isn't correct
10 Incorrect 610 ms 10736 KB Output isn't correct
11 Incorrect 653 ms 10736 KB Output isn't correct
12 Incorrect 681 ms 10736 KB Output isn't correct
13 Incorrect 653 ms 10780 KB Output isn't correct