oj.uz

Submission #57868

# Submission time Handle Problem Language Result Execution time Memory
57868 2018-07-16T12:56:11 Z thiago4532 Cake (CEOI14_cake) C++17
15 / 100
 2000 ms 3148 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;
			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+1;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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 560 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 25 ms 612 KB Output is correct
5 Correct 572 ms 928 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2047 ms 928 KB Time limit exceeded
2 Execution timed out 2068 ms 928 KB Time limit exceeded
3 Execution timed out 2072 ms 928 KB Time limit exceeded
4 Execution timed out 2048 ms 928 KB Time limit exceeded
5 Execution timed out 2057 ms 928 KB Time limit exceeded
6 Execution timed out 2059 ms 928 KB Time limit exceeded
7 Execution timed out 2076 ms 928 KB Time limit exceeded
8 Execution timed out 2051 ms 928 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 1924 KB Time limit exceeded
2 Execution timed out 2060 ms 1924 KB Time limit exceeded
3 Execution timed out 2058 ms 2004 KB Time limit exceeded
4 Correct 2 ms 2004 KB Output is correct
5 Execution timed out 2075 ms 2904 KB Time limit exceeded
6 Execution timed out 2063 ms 3148 KB Time limit exceeded
7 Execution timed out 2040 ms 3148 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 3148 KB Output is correct
2 Correct 1168 ms 3148 KB Output is correct
3 Execution timed out 2060 ms 3148 KB Time limit exceeded
4 Execution timed out 2053 ms 3148 KB Time limit exceeded
5 Correct 1309 ms 3148 KB Output is correct
6 Execution timed out 2078 ms 3148 KB Time limit exceeded
7 Execution timed out 2050 ms 3148 KB Time limit exceeded
8 Execution timed out 2045 ms 3148 KB Time limit exceeded
9 Execution timed out 2051 ms 3148 KB Time limit exceeded
10 Execution timed out 2023 ms 3148 KB Time limit exceeded
11 Execution timed out 2052 ms 3148 KB Time limit exceeded
12 Execution timed out 2050 ms 3148 KB Time limit exceeded
13 Execution timed out 2069 ms 3148 KB Time limit exceeded