oj.uz

Submission #70946

# Submission time Handle Problem Language Result Execution time Memory
70946 2018-08-23T20:00:38 Z spencercompton Cake (CEOI14_cake) C++17
0 / 100
 810 ms 3676 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 3 ms 248 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 371 ms 488 KB Output isn't correct
2 Correct 320 ms 488 KB Output is correct
3 Incorrect 364 ms 488 KB Output isn't correct
4 Correct 345 ms 492 KB Output is correct
5 Incorrect 365 ms 492 KB Output isn't correct
6 Incorrect 474 ms 620 KB Output isn't correct
7 Incorrect 407 ms 672 KB Output isn't correct
8 Correct 384 ms 672 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 200 ms 1568 KB Output isn't correct
2 Incorrect 204 ms 1628 KB Output isn't correct
3 Incorrect 196 ms 1628 KB Output isn't correct
4 Correct 3 ms 1628 KB Output is correct
5 Incorrect 209 ms 2420 KB Output isn't correct
6 Incorrect 218 ms 2532 KB Output isn't correct
7 Correct 217 ms 2532 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 2532 KB Output isn't correct
2 Incorrect 81 ms 2532 KB Output isn't correct
3 Incorrect 138 ms 2532 KB Output isn't correct
4 Incorrect 121 ms 2532 KB Output isn't correct
5 Incorrect 197 ms 2532 KB Output isn't correct
6 Incorrect 269 ms 2532 KB Output isn't correct
7 Incorrect 260 ms 2532 KB Output isn't correct
8 Incorrect 179 ms 2532 KB Output isn't correct
9 Incorrect 744 ms 3676 KB Output isn't correct
10 Incorrect 653 ms 3676 KB Output isn't correct
11 Incorrect 675 ms 3676 KB Output isn't correct
12 Incorrect 774 ms 3676 KB Output isn't correct
13 Incorrect 810 ms 3676 KB Output isn't correct