제출 #1219017

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219017		bangan	Radio Towers (IOI22_towers)	C++20	0 / 100	4062 ms	6068 KiB

towers

// Fuck It We BALL

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

#define chmax(a, b) a = max(a, b)

#define pb push_back

#define LC (v<<1)
#define RC (LC|1)
#define mid ((l+r) / 2)

const int mxn = 1e5 + 4;

int n;
int h[mxn];

struct MinRangeSeg {
	struct Node {
		int idx, val;
		Node() {}
		Node(int idx_, int val_): idx(idx_), val(val_) {}
	};
	int n;
	vector<Node> t; 
	MinRangeSeg(int n_): n(n_), t(4*n_ + 16) {}
	void pull(int v) {
		t[v] = t[LC];
		if (t[v].val > t[RC].val) t[v] = t[RC];
	}
	void set_val(int i, int x, int v, int l, int r) {
		if (r-l == 1) {
			t[v] = Node(i, x);
			return;
		}
		i<mid ? set_val(i,x, LC, l, mid) : set_val(i,x, RC, mid, r);
		pull(v);
	}
	void set_val(int i, int x) {
		set_val(i,x, 1, 0, n);
	}
	Node get_min(int s, int e, int v, int l, int r) {
		if (s<=l && r<=e) return t[v];
		if (e <= mid) return get_min(s,e, LC, l, mid);
		if (s >= mid) return get_min(s,e, RC, mid, r);
		Node L = get_min(s,e, LC, l, mid);
		Node R = get_min(s,e, RC, mid, r);
		return L.val < R.val ? L : R;
	}
	Node get_min(int s, int e) {
		return get_min(s, e, 1, 0, n);
	}
} seg_min_h(mxn);

struct MaxRangeSeg {
	struct Node {
		int idx, val;
		Node() {}
		Node(int idx_, int val_): idx(idx_), val(val_) {}
	};
	int n;
	vector<Node> t; 
	MaxRangeSeg(int n_): n(n_), t(4*n_ + 16) {}
	void pull(int v) {
		t[v] = t[LC];
		if (t[v].val < t[RC].val) t[v] = t[RC];
	}
	void set_val(int i, int x, int v, int l, int r) {
		if (r-l == 1) {
			t[v] = Node(i, x);
			return;
		}
		i<mid ? set_val(i,x, LC, l, mid) : set_val(i,x, RC, mid, r);
		pull(v);
	}
	void set_val(int i, int x) {
		set_val(i,x, 1, 0, n);
	}
	Node get_max(int s, int e, int v, int l, int r) {
		if (s<=l && r<=e) return t[v];
		if (e <= mid) return get_max(s,e, LC, l, mid);
		if (s >= mid) return get_max(s,e, RC, mid, r);
		Node L = get_max(s,e, LC, l, mid);
		Node R = get_max(s,e, RC, mid, r);
		return L.val > R.val ? L : R;
	}
	Node get_max(int s, int e) {
		return get_max(s, e, 1, 0, n);
	}
} seg_max_h(mxn);

void init(int N, std::vector<int> H) {
	n = N;
	for (int i=0; i<n; i++) h[i+1] = H[i]; 
	for (int i=1; i<=n; i++) seg_min_h.set_val(i, h[i]);
	for (int i=1; i<=n; i++) seg_max_h.set_val(i, h[i]);
}

int prv[mxn], nxt[mxn];

void prep(int d) {
	for (int i=1; i<=n; i++) {
		int l = 0, r = i;
		while (r-l > 1) {
			h[i] <= seg_max_h.get_max(mid, i).val - d ? l = mid : r = mid;
		}
		prv[i] = l;
		if (1 <= l) assert(h[i] <= h[l]-d);
	}
	for (int i=1; i<=n; i++) {
		int l = i, r = n+1;
		while (r-l > 1) {
			h[i] <= seg_max_h.get_max(i+1, mid+1).val - d ? r = mid : l = mid;
		}
		nxt[i] = r;
		if (r <= n) assert(h[i] <= h[r]-d);
	}
	for (int i=1; i<=n; i++) {
		for (int j = i-1; j>=1; j--) if (h[i] <= h[j]-d) {
			// cout << prv[i] << " correct = " << j << endl;
			// assert(prv[i]==j);
			break;
		}
	}
	for (int i=1; i<=n; i++) {
		for (int j = i+1; j<=n; j++) if (h[i] <= h[j]-d) {
			// cout << nxt[i] << " correct = " << j << endl;
			assert(nxt[i]==j);
			break;
		}
	}
}

bool DONE = false;
int max_towers(int L, int R, int D) {
	L++; R++;
	if (!DONE) {
		prep(D);
		// DONE = true;
	}
	return 0;
}

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