Submission #57867

#	Time	Username	Problem	Language	Result	Execution time	Memory
57867		thiago4532	Cake (CEOI14_cake)	C++17	0 / 100	2084 ms	2988 KiB

cake

#include <bits/stdc++.h>

using namespace std;
const int maxn = 250010;
int vet[maxn], bak[maxn], mark[maxn];

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

	node(int v=0): w(rand()), v(v), l(0), r(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;
}

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 v){
	if(!t) return void(l = r = 0);

	if(t->v < v){
		l = t;
		split(t->r, t->r, r, v);
	}else{
		r = t;
		split(t->l, l, t->l, v);
	}
	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;
	split(t, l, r, pos);
	split(r, aux, r, 2);
	merge(t, l, r);
	delete aux;
}

typedef pair<int, int> pii;
#define ff first
#define ss second

int main(){
	ios::sync_with_stdio(false), cin.tie(0);
	int n, a;
	cin >> n >> a;
	for(int i=1;i<=n;i++)
		cin >> vet[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);
			
			int maior = vet[x];

			if(x - a == 0){
				cout << ans << "\n";
				continue;
			}

			int p = a + o;

			if(x - a > 0)
			for(int i=a;i<=x;i++)
				maior = max(maior, vet[i]);
			else
			for(int i=x;i<=a;i++)
				maior = max(maior, vet[i]);
			
			//cout << "MAX: " << maior << "\n";
			while(p >= 1 && p <= n){
				//cout << p << " " << vet[p] << "\n";
				if(vet[p] > maior) break;
				ans++;
				p += o;
			}
			cout << ans << "\n";
		}else{
			int p, e;
			cin >> p >> e;
			e = n - e + 1;

			for(int i=1;i<=n;i++) bak[i] = vet[i];
			nth_element(bak+1, bak+e, bak+1+n);

			vet[p] = bak[e]+1;

			for(int i=1;i<=n;i++)
				if(i != p && vet[i] >= vet[p]) vet[i]++;
		}
	}
	return 0;
}

Compilation message (stderr)

cake.cpp: In constructor 'node::node(int)':
cake.cpp:8:9: warning: 'node::w' will be initialized after [-Wreorder]
  int v, w, sz;
         ^
cake.cpp:8:6: warning:   'int node::v' [-Wreorder]
  int v, w, sz;
      ^
cake.cpp:11:2: warning:   when initialized here [-Wreorder]
  node(int v=0): w(rand()), v(v), l(0), r(0) { }
  ^~~~

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