Submission #1056126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056126		pawned	Radio Towers (IOI22_towers)	C++17	11 / 100	4067 ms	2492 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);
	for (int j = 0; j < K; j++) {	// see if can use order[j]
//		cout<<"at "<<j<<endl;
		bool can = true;
		for (int k = 0; k < K; k++) {
			if (k == order[j])
				continue;
			if (used[k]) {
				int maxr = 0;	// max between k and order[j]
				if (k < order[j])
					maxr = st.query(k + 1, order[j]);
				else
					maxr = st.query(order[j] + 1, k);
//				cout<<k<<", "<<order[j]<<": "<<maxr<<endl;
				if (h[order[j]] > maxr - D || h[k] > maxr - D)
					can = false;
			}
		}
		if (can) {
//			cout<<"can use "<<order[j]<<endl;
			total++;
			used[order[j]] = true;
		}
	}
/*	cout<<"used: ";
	for (bool b : used)
		cout<<b<<" ";
	cout<<endl;*/
	return total;
}

// shortest to tallest, greedy (?)
// just code it up to see if it works

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