oj.uz

Submission #57867

# Submission time Handle Problem Language Result Execution time Memory
57867 2018-07-16T12:47:10 Z thiago4532 Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 2988 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;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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2044 ms 560 KB Time limit exceeded
2 Execution timed out 2057 ms 636 KB Time limit exceeded
3 Execution timed out 2074 ms 636 KB Time limit exceeded
4 Execution timed out 2060 ms 636 KB Time limit exceeded
5 Execution timed out 2080 ms 728 KB Time limit exceeded
6 Execution timed out 2075 ms 728 KB Time limit exceeded
7 Execution timed out 2072 ms 732 KB Time limit exceeded
8 Execution timed out 2065 ms 856 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 1812 KB Time limit exceeded
2 Execution timed out 2068 ms 1820 KB Time limit exceeded
3 Execution timed out 2071 ms 1856 KB Time limit exceeded
4 Incorrect 2 ms 1856 KB Output isn't correct
5 Execution timed out 2084 ms 2944 KB Time limit exceeded
6 Execution timed out 2072 ms 2988 KB Time limit exceeded
7 Execution timed out 2071 ms 2988 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 698 ms 2988 KB Output isn't correct
2 Incorrect 1257 ms 2988 KB Output isn't correct
3 Execution timed out 2053 ms 2988 KB Time limit exceeded
4 Execution timed out 2071 ms 2988 KB Time limit exceeded
5 Incorrect 1320 ms 2988 KB Output isn't correct
6 Execution timed out 2073 ms 2988 KB Time limit exceeded
7 Execution timed out 2057 ms 2988 KB Time limit exceeded
8 Execution timed out 2062 ms 2988 KB Time limit exceeded
9 Execution timed out 2053 ms 2988 KB Time limit exceeded
10 Execution timed out 2078 ms 2988 KB Time limit exceeded
11 Execution timed out 2066 ms 2988 KB Time limit exceeded
12 Execution timed out 2069 ms 2988 KB Time limit exceeded
13 Execution timed out 2059 ms 2988 KB Time limit exceeded