Submission #1280532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280532		nicolo_010	Radio Towers (IOI22_towers)	C++20	23 / 100	4093 ms	7008 KiB

towers

#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;

vector<int> h;
struct SegTree {
	vector<int> tree;
	SegTree(int n) {
		tree.assign(4*n, 0);
	}
	void query(int p, int l, int r, int i, int x) {
		if (l > i || r < i) return;
		if (l==r && r==i) {
			tree[p] = x;
			return;
		}
		int m = (l+r)/2;
		query(2*p, l, m, i, x);
		query(2*p+1, m+1, r, i, x);
		int i1 = tree[2*p];
		int i2 = tree[2*p+1];
		tree[p] = max(i1, i2);
	}
	int rmq(int p, int l, int r, int i, int j) {
		if (l > j || r < i) return 0;
		if (i <= l && r <= j) {
			return tree[p];
		}
		int m = (l+r)/2;
		int i1 = rmq(2*p, l, m, i, j);
		int i2 = rmq(2*p+1, m+1, r, i, j);
		return max(i1, i2);
	}
	int walkleft(int p, int l, int r, int x) {
		if (l==r) return l;
		int m = (l+r)/2;
		if (tree[2*p+1] >= x) {
			return walkleft(2*p+1, m+1, r, x);
		}
		else {
			return walkleft(2*p, l, m, x);
		}
	}
	int walkright(int p, int l, int r, int x) {
		if (l==r) return l;
		int m = (l+r)/2;
		if (tree[2*p] >= x) {
			return walkright(2*p, l, m, x);
		}
		else {
			return walkright(2*p+1, m+1, r, x);
		}
	} 
};

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

bool cmp(int a, int b) {
	return h[a] < h[b];
}

int max_towers(int l, int r, int d) {
	int n = h.size();
	vector<int> L(n, 0), R(n, n-1);
	SegTree mx(n);
	for (int i=0; i<n; i++) {
		L[i] = mx.walkleft(1, 0, n-1, h[i]+d);
		mx.query(1, 0, n-1, i, h[i]);
	}
	mx = SegTree(n);
	for (int i=n-1; i>=0; i--) {
		R[i] = mx.walkright(1, 0, n-1, h[i]+d);
		mx.query(1, 0, n-1, i, h[i]);
	}
	vector<int> towers;
	for (int i=l; i <= r; i++) {
		towers.push_back(i);
	}
	sort(towers.begin(), towers.end(), cmp);
	SegTree st(n);
	int cnt=0;
	int m = towers.size();
	for (int k=0; k<m; k++) {
		int i = towers[k];
		int i1 = st.rmq(1, 0, n-1, L[i], i);
		int i2 = st.rmq(1, 0, n-1, i, R[i]);
		if (i1 == i2 && i2 == 0) {
			cnt++;
			st.query(1, 0, n-1, i, 1);
		}
	}
	return cnt;
}

• 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