제출 #1056172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1056172		pawned	송신탑 (IOI22_towers)	C++17	23 / 100	4051 ms	6132 KiB

towers

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "towers.h"

struct Segtree {	// point upd, range max
	int sz;
	vi vals;
	Segtree(int N) {
		sz = 1;
		while (sz < N)
			sz *= 2;
		vals = vi(2 * sz, 0);
	}
	void upd(int pos, int val, int id, int left, int right) {
		if (right - left == 1) {
			vals[id] = val;
			return;
		}
		int mid = (left + right) / 2;
		if (pos < mid)
			upd(pos, val, 2 * id + 1, left, mid);
		else
			upd(pos, val, 2 * id + 2, mid, right);
		vals[id] = max(vals[2 * id + 1], vals[2 * id + 2]);
	}
	void upd(int pos, int val) {
		upd(pos, val, 0, 0, sz);
	}
	int query(int qleft, int qright, int id, int left, int right) {
		if (qright <= left || right <= qleft)
			return 0;
		if (qleft <= left && right <= qright)
			return vals[id];
		int mid = (left + right) / 2;
		int s1 = query(qleft, qright, 2 * id + 1, left, mid);
		int s2 = query(qleft, qright, 2 * id + 2, mid, right);
		return max(s1, s2);
	}
	int query(int qleft, int qright) {
		return query(qleft, qright, 0, 0, sz);
	}
};

int N;
vi H;
int maxv = -1;
int maxp = -1;

void init(int N_g, vi H_g) {
	N = N_g;
	H = H_g;

}

int max_towers(int L, int R, int D) {
	int K = R - L + 1;
	vi h;
	for (int j = L; j <= R; j++) {
		h.pb(H[j]);
	}
/*	cout<<"h: ";
	for (int x : h)
		cout<<x<<" ";
	cout<<endl;*/
	Segtree st(K);
	for (int j = 0; j < K; j++) {
		st.upd(j, h[j]);
	}
	vector<ii> allp;	// {height, pos}
	for (int j = 0; j < K; j++) {
		allp.pb({h[j], j});
	}
	sort(allp.begin(), allp.end());
	vi order;
	for (int j = 0; j < K; j++) {
		order.pb(allp[j].se);
	}
	int total = 0;
	vector<bool> used(K, false);
	set<int> allu;
	for (int j = 0; j < K; j++) {	// see if can use order[j]
//		cout<<"at "<<j<<endl;
		bool can = true;
		auto it = allu.lower_bound(order[j]);
		if (it != allu.begin()) {	// has to the left
			auto it2 = it;
			it2--;
			int lp = *it2;	// left position
			int maxr = st.query(lp + 1, order[j]);
			if (h[order[j]] > maxr - D)
				can = false;
		}
		if (it != allu.end()) {	// has to the right
			int rp = *it;
			int maxr = st.query(order[j] + 1, rp);
			if (h[order[j]] > maxr - D)
				can = false;
		}
		if (can) {
//			cout<<"can use "<<order[j]<<endl;
			total++;
			used[order[j]] = true;
			allu.insert(order[j]);
		}
	}
/*	cout<<"used: ";
	for (bool b : used)
		cout<<b<<" ";
	cout<<endl;*/
	return total;
}

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