oj.uz

답안 #57899

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
57899 2018-07-16T13:42:42 Z thiago4532 케이크 (CEOI14_cake) C++17
15 / 100
 2000 ms 15360 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, maior;
	node *l, *r;

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


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;
	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);
}

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;
}

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;

	node *no = 0;
	for(int i=1;i<=n;i++)
		cin >> vet[i], insert(no, i, 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]);
			

			//if(o == 1) cout << "QUERY1: " << ans_query1(no, p, maior) << "\n" ;
			//else cout << "QUERY2: " << ans_query2(no, p+1, maior) << "\n";

			//cout << "MAX: " << maior << "\n";
			/*while(p >= 1 && p <= n){
				//cout << p << " " << vet[p] << "\n";
				if(vet[p] > maior) break;
				ans++;
				p += 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;

			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;
			altera(no, p, vet[p]);

			for(int i=1;i<=n;i++)
				if(i != p && vet[i] >= vet[p]) vet[i]++, altera(no, i, vet[i]);

		}
	}
	return 0;
}

Compilation message

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

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 408 KB Output is correct
4 Correct 25 ms 644 KB Output is correct
5 Correct 524 ms 1292 KB Output is correct

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2081 ms 1292 KB Time limit exceeded
2 Execution timed out 2090 ms 1552 KB Time limit exceeded
3 Execution timed out 2088 ms 1564 KB Time limit exceeded
4 Execution timed out 2087 ms 1564 KB Time limit exceeded
5 Execution timed out 2079 ms 2476 KB Time limit exceeded
6 Execution timed out 2075 ms 2476 KB Time limit exceeded
7 Execution timed out 2078 ms 2476 KB Time limit exceeded
8 Execution timed out 2066 ms 2476 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2075 ms 7144 KB Time limit exceeded
2 Correct 1449 ms 7304 KB Output is correct
3 Correct 432 ms 7304 KB Output is correct
4 Correct 3 ms 7304 KB Output is correct
5 Execution timed out 2055 ms 15144 KB Time limit exceeded
6 Execution timed out 2070 ms 15360 KB Time limit exceeded
7 Correct 518 ms 15360 KB Output is correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 823 ms 15360 KB Output is correct
2 Correct 1363 ms 15360 KB Output is correct
3 Execution timed out 2045 ms 15360 KB Time limit exceeded
4 Execution timed out 2060 ms 15360 KB Time limit exceeded
5 Correct 1556 ms 15360 KB Output is correct
6 Execution timed out 2049 ms 15360 KB Time limit exceeded
7 Execution timed out 2074 ms 15360 KB Time limit exceeded
8 Execution timed out 2067 ms 15360 KB Time limit exceeded
9 Execution timed out 2071 ms 15360 KB Time limit exceeded
10 Execution timed out 2080 ms 15360 KB Time limit exceeded
11 Execution timed out 2072 ms 15360 KB Time limit exceeded
12 Execution timed out 2072 ms 15360 KB Time limit exceeded
13 Execution timed out 2062 ms 15360 KB Time limit exceeded