oj.uz

Submission #198576

# Submission time Handle Problem Language Result Execution time Memory
198576 2020-01-26T16:55:51 Z Atalasion Cake (CEOI14_cake) C++14
0 / 100
 717 ms 14356 KB 
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimise ("ofast")
#pragma GCC optimise("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 250000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000000000000000;
const ll LOG = 25;

int n, q, tim[N], lazy[N << 2], s, a[N], koj[N];

vector<int> Top;

void modify(int id, int x){
	lazy[id] = x;
}

void shift(int id){
	if (lazy[id] == -1) return;
	modify(id << 1, lazy[id]);
	modify(id << 1 | 1, lazy[id]);
	lazy[id] = -1;
}

void SET(int id, int lq, int rq, int x, int l, int r){
	if (rq <= l || r <= lq) return;
	if (lq <= l && r <= rq){
		modify(id, x);
		return;
	}
	int md = (l + r) >> 1;
	shift(id);
	SET(id << 1, lq, rq, x, l, md);
	SET(id << 1 | 1, lq, rq, x, md, r);
}

int get(int id, int lq, int rq, int l, int r){
	if (rq <= l || r <= lq) return 0;
	if (lq <= l && r <= rq){
		return lazy[id];
	}
	shift(id);
	int md = (l + r) >> 1;
	return (get(id << 1, lq, rq, l, md) + get(id << 1 | 1, lq, rq, md, r));
}

inline void build(){
	int l = s - 1, r = s + 1;
	SET(1, s, s + 1, l, 1, n + 1);
	while (l != 0 || r != n + 1){
		//cout << l << ' ' << r << '\n';
		if (a[l] < a[r]){
			SET(1, l, l + 1, r, 1, n + 1);
			l--;
		}else{
			SET(1, r, r + 1, l, 1, n + 1);
			r++;
		}
	}
}

inline void APPEND(int x, int y){
	vector<int> t;
	bool f = 0;
	for (auto u:Top){
		if (u == x) f = 1;
		else t.pb(u);
	}
	Top.clear();
	if (f){
		int pnt = 0;
		for (int i = 0; i <= min(n - 1, 9); i++){
			if (i == min(n - 1, 9) - (n - y)) Top.pb(x);
			else Top.pb(t[pnt++]);
		}
		return;
	}
	int pnt = 1;
	for (int i = 0; i <= min(n - 1, 9); i++){
		if (i == min(n - 1, 9) - (n - y)) t.pb(x);
		else t.pb(Top[i]);
	}
}

inline void solve(int x, int y){
	APPEND(x, y);
	Top.pb(0);
	Top.pb(n + 1);
	//cout << "YES\n";
	//for (auto u:Top) cout << u << ' ';
	//cout << '\n';
	if (x == s) return;
	int l, r;
	bool f = 0;
	if (x > s) l = get(1, x, x + 1, 1, n + 1), r = x;
	else l = x, r = get(1, x, x + 1, 1, n + 1), f = 1;
	int pnt = min(n - 1, 9) - (n - y);
	//cout << "YES" << endl;
	//cout << pnt << '\n';
	while (l > 0 || r < n + 1){
		//cout << l << ' ' << r << endl;
		if (f){
			int mn = n + 1, id = -1;
			for (int i = pnt + 1; i < Top.size(); i++){
				if (Top[i] >= r){
					if (mn == n + 1) {mn = Top[i]; id = i;}
					else if (mn > Top[i]){
						mn = Top[i];
						id = i;
					}
				}
			}
			//cout << mn << '\n';
			SET(1, r, mn, l, 1, n + 1);
			SET(1, l, l + 1, mn, 1, n + 1);
			r = mn;
			f = 0;
			pnt = id;
			l--;
		}else{
			int mx = 0, id = -1;
			for (int i = pnt + 1; i < Top.size(); i++){
				if (Top[i] <= l){
					if (mx < Top[i]) mx = Top[i], id = i;
				}
			}
			//cout << mx << endl;
			SET(1, mx + 1, l + 1, r, 1, n + 1);
			SET(1, r, r + 1, mx, 1, n + 1);
			l = mx;
			f = 1;
			pnt = id;
			r++;
		}
		
	}
	//cout << "YES2" << endl;
	 
	Top.pop_back();
	Top.pop_back();
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> s;
	a[0] = n + 1, a[n + 1] = n + 1;
	memset(lazy, -1, sizeof lazy);
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		koj[a[i]] = i;
	}
	for (int i = min(9, n - 1); i >= 0; i--){
		Top.pb(koj[n - i]);
	}
	cin >> q;
	build();
	while (q--){
		char c;
		cin >> c;
		if (c == 'F'){
			int x;
			cin >> x;
			int id = get(1, x, x + 1, 1, n + 1);
			cout << abs(id - x) - 1 << '\n';
		}else{
			int x, y;
			cin >> x >> y;
			y = n - y + 1;
			//cout << "YES" << endl;
			solve(x, y);
			//cout << "YES2" << endl;
		}
	}











	return 0;
}

/*
5 3
5 1 2 4 3
1
E 2 1
*/

/*
5 3
5 1 2 4 3
7
E 2 1
E 5 2
F 1
F 2
F 3
F 4
F 5
*/

Compilation message

cake.cpp:8:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
 #pragma GCC optimise ("ofast")
 
cake.cpp:9:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
 #pragma GCC optimise("unroll-loops")
 
cake.cpp: In function 'void APPEND(int, int)':
cake.cpp:90:6: warning: unused variable 'pnt' [-Wunused-variable]
  int pnt = 1;
      ^~~
cake.cpp: In function 'void solve(int, int)':
cake.cpp:116:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = pnt + 1; i < Top.size(); i++){
                          ~~^~~~~~~~~~~~
cake.cpp:134:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = pnt + 1; i < Top.size(); i++){
                          ~~^~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4216 KB Output is correct
2 Incorrect 7 ms 4216 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 448 ms 8800 KB Output isn't correct
2 Incorrect 449 ms 8824 KB Output isn't correct
3 Incorrect 417 ms 8824 KB Output isn't correct
4 Correct 636 ms 8952 KB Output is correct
5 Incorrect 514 ms 9184 KB Output isn't correct
6 Incorrect 490 ms 9756 KB Output isn't correct
7 Incorrect 464 ms 9264 KB Output isn't correct
8 Correct 717 ms 9888 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 7032 KB Output isn't correct
2 Incorrect 75 ms 6904 KB Output isn't correct
3 Incorrect 70 ms 6888 KB Output isn't correct
4 Correct 8 ms 4216 KB Output is correct
5 Incorrect 129 ms 9508 KB Output isn't correct
6 Incorrect 116 ms 9336 KB Output isn't correct
7 Correct 104 ms 9080 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 4856 KB Output isn't correct
2 Incorrect 42 ms 4856 KB Output isn't correct
3 Incorrect 81 ms 5752 KB Output isn't correct
4 Incorrect 85 ms 5752 KB Output isn't correct
5 Incorrect 107 ms 5692 KB Output isn't correct
6 Incorrect 142 ms 6932 KB Output isn't correct
7 Incorrect 190 ms 6392 KB Output isn't correct
8 Incorrect 231 ms 7672 KB Output isn't correct
9 Incorrect 514 ms 14328 KB Output isn't correct
10 Incorrect 340 ms 9212 KB Output isn't correct
11 Incorrect 389 ms 10104 KB Output isn't correct
12 Incorrect 512 ms 13448 KB Output isn't correct
13 Incorrect 470 ms 14356 KB Output isn't correct