제출 #198576

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
198576		Atalasion	케이크 (CEOI14_cake)	C++14	0 / 100	717 ms	14356 KiB

cake

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

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50