제출 #748812

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
748812		QwertyPi	송신탑 (IOI22_towers)	C++17	17 / 100	1624 ms	110424 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

namespace solve{
	int N; vector<int> H;
	vector<bool> active;
	struct node{
		int l, r, s; node *ll, *rr;
		node(int l, int r, int s = 1) : l(l), r(r), s(s), ll(0), rr(0) {};
		node(node *ll, node *rr) : l(ll->l), r(rr->r), s(ll->s + rr->s), ll(ll), rr(rr) {};
	};
	
	map<int, node*> ans;
	
	node* build(int l, int r){
		node* p = new node(l, r);
		if (l != r) {
			int m = (l + r) / 2;
			p->ll = build(l, m);
			p->rr = build(m + 1, r);
			p->s = p->ll->s + p->rr->s;
		} else {
			p->s = active[l];
		}
		return p;
	}
	
	node* update(node* root, int p, int v){
		if(root->l == root->r)
			return new node(root->l, root->r, v);
		
		if(p <= root->ll->r){
			node *x = update(root->ll, p, v);
			node *y = root->rr;
			return new node(x, y);
		}else{
			node *x = root->ll;
			node *y = update(root->rr, p, v);
			return new node(x, y);
		}
	}
	
	void crawl(node* v, bool ini = true){
		if(v == nullptr)
			return;
		if(v->ll || v->rr) {
			crawl(v->ll, false);
			crawl(v->rr, false);
		} else {
			cout << v->s << ' ';
		}
		if (ini) {
			cout << endl;
		}
	}
	
	int query(node* v, int l, int r){
		if(v->r < l || r < v->l)
			return 0;
		if(l <= v->l && v->r <= r)
			return v->s;
		int x = query(v->ll, l, r);
		int y = query(v->rr, l, r);
		return x + y;
	}
	
	int kth(node* v, int k){
		if(v->l == v->r)
			return v->l;
		if(k <= v->ll->s)
			return kth(v->ll, k);
		else
			return kth(v->rr, k - v->ll->s);
	}
	
	int Min[20][100001], Max[20][100001];
	
	int getMin(int l, int r){
		int d = __lg(r - l + 1);
		return H[Min[d][l]] < H[Min[d][r - (1 << d) + 1]] ? Min[d][l] : Min[d][r - (1 << d) + 1];
	}
	int getMax(int l, int r){
		int d = __lg(r - l + 1);
		return H[Max[d][l]] > H[Max[d][r - (1 << d) + 1]] ? Max[d][l] : Max[d][r - (1 << d) + 1];
	}
	
	void init(){
		set<pair<int, int>> T;
		set<pair<int, pair<int, int>>> S;
		active = vector<bool>(N, true);
		for(int i = 0; i < N; i++){
			if(i > 0 && i < N - 1 && ((H[i - 1] <= H[i] && H[i] <= H[i + 1]) || (H[i - 1] >= H[i] && H[i] >= H[i + 1]))) {
				active[i] = false;
				continue;
			}
			T.insert({i, H[i]});
		}
		
		if (T.size() >= 2 && (T.begin())->se > next(T.begin())->se) {
			active[T.begin()->fi] = false;
			T.erase(T.begin());
		}
		
		if (T.size() >= 2 && prev(T.end())->se > prev(prev(T.end()))->se) {
			active[prev(T.end())->fi] = false;
			T.erase(prev(T.end()));
		}
		/*
		cout << "D = 0" << endl;
		for(auto t : T){
			cout << "[" << t.fi << "] => " << t.se << endl;
		}
		*/
		ans[0] = build(0, N - 1);
		
		for(auto t = T.begin(); t != T.end(); t++){
			if(t != T.begin()) {
				S.insert({abs(t->se - prev(t)->se), {t->fi, prev(t)->fi}});
			}
		}
		
		for(int i = 0; i < N; i++) Min[0][i] = i;
		for(int j = 1; j < 20; j++) for(int i = 0; i <= N - (1 << j); i++) Min[j][i] = H[Min[j - 1][i]] < H[Min[j - 1][i + (1 << j - 1)]] ? Min[j - 1][i] : Min[j - 1][i + (1 << j - 1)];
		for(int i = 0; i < N; i++) Max[0][i] = i;
		for(int j = 1; j < 20; j++) for(int i = 0; i <= N - (1 << j); i++) Max[j][i] = H[Max[j - 1][i]] > H[Max[j - 1][i + (1 << j - 1)]] ? Max[j - 1][i] : Max[j - 1][i + (1 << j - 1)];

		node* cur = ans[0];
		while(S.size()){
			auto [d, p] = *S.begin(); S.erase(S.begin());
			
			int x = p.fi, y = p.se;
			if(!active[x] || !active[y])
				continue;
			
			active[x] = active[y] = false;

			auto ptr = T.lower_bound({x, -1});
			if(ptr != T.end() && ptr->fi == x)
				T.erase(ptr);
			
			ptr = T.lower_bound({y, -1});
			if(ptr != T.end() && ptr->fi == y)
				T.erase(ptr); 
			
			ptr = T.lower_bound({y, -1});
			if (ptr != T.begin() && ptr != T.end()) {
				S.insert({abs(ptr->se - prev(ptr)->se), {ptr->fi, prev(ptr)->fi}});
			}
			/*
			cout << "D = " << d << endl;
			for(auto t : T){
				cout << "[" << t.fi << "] => " << t.se << endl;
			}
			*/
			cur = update(cur, x, 0);
			cur = update(cur, y, 0);
			ans[d + 1] = cur;
		}
	}
	
	int query(int L, int R, int D) {
		node *root = (--ans.upper_bound(D))->se;
		int s_L = query(root, 0, L - 1);
		int s = query(root, L, R);
		if(s <= 1) return 1;
		
		int L1 = kth(root, s_L + 1);
		int L2 = kth(root, s_L + 2);
		
		int R1 = kth(root, s_L + s);
		int R2 = kth(root, s_L + s - 1);
		
		int a = s;
		if (H[L1] > H[L2]) {
			--a;
			if(L < L1){
				int L0 = getMin(L, L1 - 1);
				if(H[L1] - H[L0] >= D){
					a += 2;
				}
			}
		}
		
		if (H[R1] > H[R2]) {
			--a;
			if(R > R1){
				int R0 = getMin(R1 + 1, R);
				if(H[R1] - H[R0] >= D){
					a += 2;
				}
			}
		} 
		return (a + 1) / 2;
	}
};

void init(int N, vector<int> H) {
	solve::N = N;
	solve::H = H;
	solve::init();
}

int max_towers(int L, int R, int D) {
	return solve::query(L, R, D);
}

컴파일 시 표준 에러 (stderr) 메시지

towers.cpp: In function 'void solve::init()':
towers.cpp:127:126: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  127 |   for(int j = 1; j < 20; j++) for(int i = 0; i <= N - (1 << j); i++) Min[j][i] = H[Min[j - 1][i]] < H[Min[j - 1][i + (1 << j - 1)]] ? Min[j - 1][i] : Min[j - 1][i + (1 << j - 1)];
      |                                                                                                                            ~~^~~
towers.cpp:127:174: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  127 |   for(int j = 1; j < 20; j++) for(int i = 0; i <= N - (1 << j); i++) Min[j][i] = H[Min[j - 1][i]] < H[Min[j - 1][i + (1 << j - 1)]] ? Min[j - 1][i] : Min[j - 1][i + (1 << j - 1)];
      |                                                                                                                                                                            ~~^~~
towers.cpp:129:126: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  129 |   for(int j = 1; j < 20; j++) for(int i = 0; i <= N - (1 << j); i++) Max[j][i] = H[Max[j - 1][i]] > H[Max[j - 1][i + (1 << j - 1)]] ? Max[j - 1][i] : Max[j - 1][i + (1 << j - 1)];
      |                                                                                                                            ~~^~~
towers.cpp:129:174: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  129 |   for(int j = 1; j < 20; j++) for(int i = 0; i <= N - (1 << j); i++) Max[j][i] = H[Max[j - 1][i]] > H[Max[j - 1][i + (1 << j - 1)]] ? Max[j - 1][i] : Max[j - 1][i + (1 << j - 1)];
      |                                                                                                                                                                            ~~^~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 17 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23