oj.uz

Submission #57862

# Submission time Handle Problem Language Result Execution time Memory
57862 2018-07-16T12:31:34 Z thiago4532 Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 24264 KB 
#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, ans=0;
			cin >> x;

			for(int i=1;i<=n;i++) mark[i] = 0;
			priority_queue<pii, vector<pii>, greater<pii>> fila;
			fila.push({vet[a], a});

			while(!fila.empty()){
				if(fila.top().ss == x) break;
				int u = fila.top().ss;
				fila.pop();

				if(mark[u]) continue;
				mark[u] = 1;



				++ans;

				if(u != 1) fila.push({vet[u-1], u-1});
				if(u != n) fila.push({vet[u+1], u+1});
			}
			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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 133 ms 928 KB Output is correct
5 Execution timed out 2059 ms 1256 KB Time limit exceeded

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2056 ms 1284 KB Time limit exceeded
2 Execution timed out 2076 ms 1764 KB Time limit exceeded
3 Execution timed out 2074 ms 2276 KB Time limit exceeded
4 Execution timed out 2049 ms 2660 KB Time limit exceeded
5 Execution timed out 2045 ms 3100 KB Time limit exceeded
6 Execution timed out 2066 ms 3652 KB Time limit exceeded
7 Execution timed out 2064 ms 3916 KB Time limit exceeded
8 Execution timed out 2069 ms 4524 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2053 ms 5656 KB Time limit exceeded
2 Execution timed out 2041 ms 7476 KB Time limit exceeded
3 Execution timed out 2061 ms 8260 KB Time limit exceeded
4 Correct 3 ms 8260 KB Output is correct
5 Execution timed out 2059 ms 10008 KB Time limit exceeded
6 Execution timed out 2065 ms 11844 KB Time limit exceeded
7 Execution timed out 2055 ms 16920 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2082 ms 16920 KB Time limit exceeded
2 Execution timed out 2050 ms 16920 KB Time limit exceeded
3 Execution timed out 2072 ms 16920 KB Time limit exceeded
4 Execution timed out 2073 ms 16920 KB Time limit exceeded
5 Execution timed out 2080 ms 16920 KB Time limit exceeded
6 Execution timed out 2079 ms 16920 KB Time limit exceeded
7 Execution timed out 2074 ms 16920 KB Time limit exceeded
8 Execution timed out 2045 ms 16920 KB Time limit exceeded
9 Execution timed out 2066 ms 20104 KB Time limit exceeded
10 Execution timed out 2073 ms 20104 KB Time limit exceeded
11 Execution timed out 2069 ms 20104 KB Time limit exceeded
12 Execution timed out 2071 ms 21848 KB Time limit exceeded
13 Execution timed out 2069 ms 24264 KB Time limit exceeded