Submission #58076

#	Time	Username	Problem	Language	Result	Execution time	Memory
58076		thiago4532	케이크 (CEOI14_cake)	C++17	0 / 100	2085 ms	27000 KiB

cake

#include <bits/stdc++.h>

using namespace std;
const int maxn = 250010;
int vet[maxn], bak[maxn], mark[maxn];
typedef pair<int, int> pii;
#define ff first
#define ss second

struct node{
	int v, w, sz, maior;
	node *l, *r;

	node(int v=0): w(rand()), maior(v), v(v), l(0), r(0), sz(1) { }
};

inline int maior(node* t){
	return t ? t->maior : 0;
}

inline int sz(node *t){
	return t ? t->sz : 0;
}

inline void update(node*& t){
	if(!t) return;
	t->sz = sz(t->l) + sz(t->r) + 1;
	t->maior = max(t->v, max(maior(t->l), maior(t->r)));
}

void merge(node*& t, node* l, node *r){
	if(!l || !r) return void(t = l?l:r);

	if(l->w >= r->w){
		merge(l->r, l->r, r);
		t = l;
	}else{
		merge(r->l, l, r->l);
		t = r;
	}
	update(t);
}

void split(node *t, node*& l, node*& r, int p){
	if(!t) return void(l = r = 0);

	int pos = sz(t->l) + 1;
	if(pos < p){
		l = t;
		split(t->r, t->r, r, p-pos);
	}else{
		r = t;
		split(t->l, l, t->l, p);
	}
	update(t);
}

void insert(node*& t, int pos, int v){
	node *l=0, *r=0, *it = new node(v);
	split(t, l, r, pos);
	merge(l, l, it);
	merge(t, l, r);
}

void erase(node*& t, int pos){
	node *l=0, *r=0, *aux=0;
	split(t, l, r, pos);
	split(r, aux, r, 2);
	merge(t, l, r);
	delete aux;
}

void altera(node*& t, int p, int v){
	if(!t) return;
	int pos = sz(t->l) + 1;

	if(pos == p) t->v = v;
	else if(p < pos) altera(t->l, p, v);
	else altera(t->r, p-pos, v);

	update(t);
}

struct node2{
	int w, sz;
	node2 *l, *r;
	pii key;

	node2(pii key=pii{0, 0}): w(rand()), key(key), l(0), r(0), sz(1) { }
};

inline int sz(node2 *t){
	return t ? t->sz : 0;
}

inline void update(node2*& t){
	if(!t) return;
	t->sz = sz(t->l) + sz(t->r) + 1;
}

void merge(node2*& t, node2* l, node2 *r){
	if(!l || !r) return void(t = l?l:r);

	if(l->w >= r->w){
		merge(l->r, l->r, r);
		t = l;
	}else{
		merge(r->l, l, r->l);
		t = r;
	}
	update(t);
}

void split(node2 *t, node2*& l, node2*& r, pii key){
	if(!t) return void(l = r = 0);

	if(t->key < key){
		l = t;
		split(t->r, t->r, r, key);
	}else{
		r = t;
		split(t->l, l, t->l, key);
	}
	update(t);
}

void insert(node2*& t, pii key){
	node2 *l=0, *r=0, *it = new node2(key);
	split(t, l, r, key);
	merge(l, l, it);
	merge(t, l, r);
}

void erase(node2*& t, pii pos){
	node2 *l=0, *r=0, *aux=0;
	split(t, l, r, pos);
	split(r, aux, r, {pos.ff+1, pos.ss+1});
	merge(t, l, r);
	delete aux;
}

ostream& operator<<(ostream& out, node *t){
	if(!t) return out;
	out << t->l << t->v << " " << t->r;
}

int query1(node *t, int v, int p=0){
	if(!t) return 0;

	int pos = sz(t->l) + 1 + p;

	if(maior(t->l) >= v) return query1(t->l, v, p);
	else if(t->v >= v) return pos;
	else return query1(t->r, v, pos);
}

int query2(node *t, int v, int p=0){
	if(!t) return 0;

	int pos = sz(t->l) + 1 + p;

	if(maior(t->r) >= v) return query2(t->r, v, pos);
	else if(t->v >= v) return pos;
	else return query2(t->l, v, p);
}

inline int ans_query1(node*& t, int p, int v){
	node *l=0, *r=0;
	split(t, l, r, p);
	int resp = query1(r, v);
	//cout << r << "- " << resp << "\n";
	merge(t, l, r);
	return resp;
}

inline int ans_query2(node*& t, int p, int v){
	node *l=0, *r=0;
	split(t, l, r, p);

	int resp = query2(l, v);
	//cout << l << "- " << resp << "\n";
	merge(t, l, r);
	return resp;
}

int getMax(node*& no, int a, int b){
	if(a > b) swap(a, b);
	node *l=0, *r=0, *aux=0;
	split(no, l, r, b+1);
	split(l, aux, l, a);
	int resp = maior(l);
	merge(l, aux, l);
	merge(no, l, r);
	return resp;
}

ostream& operator<<(ostream& out, node2 *t){
	if(!t) return out;
	out << t->l << "(" << t->key.ff << ", " << t->key.ss << ") " << t->r;
	return out;
}

pii get(node2*& t, int p){
	if(!t) return {0, 0};
	int pos = sz(t->l) + 1;
	if(pos == p) return t->key;
	else if(p < pos) return get(t->l, p);
	else return get(t->r, p-pos);	
}

pii find(node2 *t, int p){
	if(!t) return {-1, -1};
	int pos = sz(t->l) + 1;

	if(pos == p) return t->key;
	else if(p < pos) return find(t->l, p);
	return find(t->r, p-pos);
}

int main(){
	ios::sync_with_stdio(false), cin.tie(0);
	int n, a;
	cin >> n >> a;
	node *no = 0;
	node2* op = 0;

	for(int i=1;i<=n;i++)
		cin >> vet[i], insert(no, i, vet[i]), insert(op, {vet[i], i});

	int q;
	cin >> q;
	while(q--){
		char c;
		cin >> c;
		if(c == 'F'){
			int x;
			cin >> x;

			int ans = abs(x - a);
			int o = (x - a > 0 ? -1 : 1);
			
			if(x - a == 0){
			

				cout << ans << "\n";
				continue;
			}

			int p = a + o;
			int maior = getMax(no, x, a-o);

			if(o == 1){	
				int y = ans_query1(no, p, maior);
				if(y == 0) ans += (n-a);
				else ans += (y-1);
			}
			else{
				int y = ans_query2(no, p+1, maior);
				if(y == 0) ans += (a-1);
				else ans += (a-y-1);
			}

			cout << ans << "\n";
		}else{
			int p, e;
			cin >> p >> e;
			e = n - e + 1;

			vector<int> puxa;

			auto k = get(op, e).ss+1;
			for(auto i=find(op, k++);i!=pii{-1, -1};i = find(op, k++))
				puxa.push_back(i.ss);

			for(auto& e : puxa){
				vet[e]++;
				altera(no, e, vet[e]);
				erase(op, {vet[e]-1, e});
				insert(op, {vet[e], e});
			}
		}
	}
	return 0;
}

Compilation message (stderr)

cake.cpp: In constructor 'node::node(int)':
cake.cpp:11:16: warning: 'node::maior' will be initialized after [-Wreorder]
  int v, w, sz, maior;
                ^~~~~
cake.cpp:11:6: warning:   'int node::v' [-Wreorder]
  int v, w, sz, maior;
      ^
cake.cpp:14:2: warning:   when initialized here [-Wreorder]
  node(int v=0): w(rand()), maior(v), v(v), l(0), r(0), sz(1) { }
  ^~~~
cake.cpp:12:12: warning: 'node::r' will be initialized after [-Wreorder]
  node *l, *r;
            ^
cake.cpp:11:12: warning:   'int node::sz' [-Wreorder]
  int v, w, sz, maior;
            ^~
cake.cpp:14:2: warning:   when initialized here [-Wreorder]
  node(int v=0): w(rand()), maior(v), v(v), l(0), r(0), sz(1) { }
  ^~~~
cake.cpp: In constructor 'node2::node2(pii)':
cake.cpp:87:6: warning: 'node2::key' will be initialized after [-Wreorder]
  pii key;
      ^~~
cake.cpp:86:9: warning:   'node2* node2::l' [-Wreorder]
  node2 *l, *r;
         ^
cake.cpp:89:2: warning:   when initialized here [-Wreorder]
  node2(pii key=pii{0, 0}): w(rand()), key(key), l(0), r(0), sz(1) { }
  ^~~~~
cake.cpp:86:13: warning: 'node2::r' will be initialized after [-Wreorder]
  node2 *l, *r;
             ^
cake.cpp:85:9: warning:   'int node2::sz' [-Wreorder]
  int w, sz;
         ^~
cake.cpp:89:2: warning:   when initialized here [-Wreorder]
  node2(pii key=pii{0, 0}): w(rand()), key(key), l(0), r(0), sz(1) { }
  ^~~~~
cake.cpp: In function 'std::ostream& operator<<(std::ostream&, node*)':
cake.cpp:145:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50