oj.uz

답안 #58076

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58076 2018-07-16T18:07:12 Z thiago4532 케이크 (CEOI14_cake) C++17
0 / 100
 2000 ms 27000 KB 
#include <bits/stdc++.h>

using namespace std;
const int maxn = 250010;
int vet[maxn], bak[maxn], mark[maxn];
typedef pair<int, int> pii;
#define ff first
#define ss second

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

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

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

struct node2{
	int w, sz;
	node2 *l, *r;
	pii key;

	node2(pii key=pii{0, 0}): w(rand()), key(key), l(0), r(0), sz(1) { }
};

inline int sz(node2 *t){
	return t ? t->sz : 0;
}

inline void update(node2*& t){
	if(!t) return;
	t->sz = sz(t->l) + sz(t->r) + 1;
}

void merge(node2*& t, node2* l, node2 *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(node2 *t, node2*& l, node2*& r, pii key){
	if(!t) return void(l = r = 0);

	if(t->key < key){
		l = t;
		split(t->r, t->r, r, key);
	}else{
		r = t;
		split(t->l, l, t->l, key);
	}
	update(t);
}

void insert(node2*& t, pii key){
	node2 *l=0, *r=0, *it = new node2(key);
	split(t, l, r, key);
	merge(l, l, it);
	merge(t, l, r);
}

void erase(node2*& t, pii pos){
	node2 *l=0, *r=0, *aux=0;
	split(t, l, r, pos);
	split(r, aux, r, {pos.ff+1, pos.ss+1});
	merge(t, l, r);
	delete aux;
}

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

int getMax(node*& no, int a, int b){
	if(a > b) swap(a, b);
	node *l=0, *r=0, *aux=0;
	split(no, l, r, b+1);
	split(l, aux, l, a);
	int resp = maior(l);
	merge(l, aux, l);
	merge(no, l, r);
	return resp;
}

ostream& operator<<(ostream& out, node2 *t){
	if(!t) return out;
	out << t->l << "(" << t->key.ff << ", " << t->key.ss << ") " << t->r;
	return out;
}

pii get(node2*& t, int p){
	if(!t) return {0, 0};
	int pos = sz(t->l) + 1;
	if(pos == p) return t->key;
	else if(p < pos) return get(t->l, p);
	else return get(t->r, p-pos);	
}

pii find(node2 *t, int p){
	if(!t) return {-1, -1};
	int pos = sz(t->l) + 1;

	if(pos == p) return t->key;
	else if(p < pos) return find(t->l, p);
	return find(t->r, p-pos);
}

int main(){
	ios::sync_with_stdio(false), cin.tie(0);
	int n, a;
	cin >> n >> a;
	node *no = 0;
	node2* op = 0;

	for(int i=1;i<=n;i++)
		cin >> vet[i], insert(no, i, vet[i]), insert(op, {vet[i], 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);
			
			if(x - a == 0){
			

				cout << ans << "\n";
				continue;
			}

			int p = a + o;
			int maior = getMax(no, x, a-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;

			vector<int> puxa;

			auto k = get(op, e).ss+1;
			for(auto i=find(op, k++);i!=pii{-1, -1};i = find(op, k++))
				puxa.push_back(i.ss);

			for(auto& e : puxa){
				vet[e]++;
				altera(no, e, vet[e]);
				erase(op, {vet[e]-1, e});
				insert(op, {vet[e], e});
			}
		}
	}
	return 0;
}

Compilation message

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

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2035 ms 1384 KB Time limit exceeded
2 Execution timed out 2056 ms 1440 KB Time limit exceeded
3 Execution timed out 2057 ms 1616 KB Time limit exceeded
4 Execution timed out 2058 ms 1616 KB Time limit exceeded
5 Execution timed out 2068 ms 3168 KB Time limit exceeded
6 Execution timed out 2070 ms 3228 KB Time limit exceeded
7 Execution timed out 2074 ms 3392 KB Time limit exceeded
8 Execution timed out 2063 ms 3392 KB Time limit exceeded

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2048 ms 11116 KB Time limit exceeded
2 Execution timed out 2062 ms 11260 KB Time limit exceeded
3 Execution timed out 2078 ms 11388 KB Time limit exceeded
4 Incorrect 2 ms 11388 KB Output isn't correct
5 Execution timed out 2076 ms 26404 KB Time limit exceeded
6 Execution timed out 2065 ms 27000 KB Time limit exceeded
7 Execution timed out 2073 ms 27000 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2076 ms 27000 KB Time limit exceeded
2 Execution timed out 2061 ms 27000 KB Time limit exceeded
3 Execution timed out 2085 ms 27000 KB Time limit exceeded
4 Execution timed out 2055 ms 27000 KB Time limit exceeded
5 Execution timed out 2082 ms 27000 KB Time limit exceeded
6 Execution timed out 2069 ms 27000 KB Time limit exceeded
7 Execution timed out 2075 ms 27000 KB Time limit exceeded
8 Execution timed out 2071 ms 27000 KB Time limit exceeded
9 Execution timed out 2071 ms 27000 KB Time limit exceeded
10 Execution timed out 2064 ms 27000 KB Time limit exceeded
11 Execution timed out 2052 ms 27000 KB Time limit exceeded
12 Execution timed out 2041 ms 27000 KB Time limit exceeded
13 Execution timed out 2069 ms 27000 KB Time limit exceeded