Submission #604291

#	Time	Username	Problem	Language	Result	Execution time	Memory
604291		GusterGoose27	Two Antennas (JOI19_antennas)	C++11	24 / 100	3079 ms	453528 KiB

antennas

#pragma GCC optimize("O3")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 2e5;
const int inf = 1e9;
const int bsize = 2e5;
const int MAX_blocks = 1;
pii valid_dists[MAXN];
int height[MAXN];
bool active[MAXN];
vector<int> toggle_l[MAXN]; // actual station is to the left
vector<int> toggle_r[MAXN]; // station to the right
int bsize_precomp[MAX_blocks][MAX_blocks]; // 
int num_blocks = 0;
int n, q;

class stree {
public:
	int mn = inf;
	int mx = 0;
	stree *l = nullptr;
	stree *r = nullptr;
	int lp, rp;
	stree(int lv, int rv) {
		lp = lv;
		rp = rv;
		if (lp == rp) {
			if (active[lp]) {
				mn = height[lp];
				mx = height[lp];
			}
		}
		else {
			int m = (lp+rp)/2;
			l = new stree(lp, m);
			r = new stree(m+1, rp);
			mn = min(l->mn, r->mn);
			mx = max(l->mx, r->mx);
		}
	}
	stree(stree *lt, stree *rt) {
		l = lt;
		r = rt;
		mn = min(l->mn, r->mn);
		mx = max(l->mx, r->mx);
		lp = l->lp;
		rp = r->rp;
	}
	int mx_in_range(int lv, int rv) {
		if (lp > rv || rp < lv) return 0;
		if (lp >= lv && rp <= rv) return mx;
		return max(l->mx_in_range(lv, rv), r->mx_in_range(lv, rv));
	}
	int mn_in_range(int lv, int rv) {
		if (lp > rv || rp < lv) return inf;
		if (lp >= lv && rp <= rv) return mn;
		return min(l->mn_in_range(lv, rv), r->mn_in_range(lv, rv));
	}
	pii diff_in_range(int lv, int rv) {
		if (lp > rv || rp < lv) return pii(inf, 0);
		if (lp >= lv && rp <= rv) return pii(mn, mx);
		pii a = l->diff_in_range(lv, rv);
		pii b = r->diff_in_range(lv, rv);
		return pii(min(a.first, b.first), max(a.second, b.second));
		//return max(, r->mx_in_range(lv, rv));
	}
	stree *update(int p) {
		if (lp > p || rp < p) return this;
		if (lp == p && rp == p) {
			return new stree(p, p);
		}
		return new stree(l->update(p), r->update(p));
	}
};

stree *l_stats[MAXN]; // station to the left
stree *r_stats[MAXN]; // station to the right

int mxdif_l(int i, int r) {
	if (r > i-valid_dists[i].first) return -1;
	int mn = l_stats[i]->mn_in_range(max(r, i-valid_dists[i].second), i-valid_dists[i].first);
	int mx = l_stats[i]->mx_in_range(max(r, i-valid_dists[i].second), i-valid_dists[i].first);
	return max(height[i]-mn, mx-height[i]);
}

int mxdif_r(int i, int l) {
	if (l < i+valid_dists[i].first) return -1;
	int mn = r_stats[i]->mn_in_range(i+valid_dists[i].first, min(l, i+valid_dists[i].second));
	int mx = r_stats[i]->mx_in_range(i+valid_dists[i].first, min(l, i+valid_dists[i].second));
	return max(height[i]-mn, mx-height[i]);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	num_blocks = n/bsize;
	for (int i = 0; i < n; i++) {
		int x, y; cin >> height[i] >> x >> y;
		valid_dists[i] = pii(x, y);
		if (x+i < n) toggle_l[x+i].push_back(i);
		if (i+y+1 < n) toggle_l[i+y+1].push_back(i);
		if (i-x >= 0) toggle_r[i-x].push_back(i);
		if (i-y-1 >= 0) toggle_r[i-y-1].push_back(i);
	}
	stree *cur_tree = new stree(0, n-1);
	for (int i = 0; i < n; i++) {
		for (int v: toggle_l[i]) {
			active[v] = 1-active[v];
			cur_tree = cur_tree->update(v);
		}
		l_stats[i] = cur_tree;
	}
	fill(active, active+n, 0);
	cur_tree = new stree(0, n-1);
	for (int i = n-1; i >= 0; i--) {
		for (int v: toggle_r[i]) {
			active[v] = 1-active[v];
			cur_tree = cur_tree->update(v);
		}
		r_stats[i] = cur_tree;
	}
	for (int i = 0; i < num_blocks; i++) {
		for (int j = i; j < num_blocks; j++) {
			if (i == j) {
				int r = bsize*i;
				int best = -1;
				for (int k = bsize*i+1; k < bsize*(i+1); k++) {
					best = max(best, mxdif_l(k, r));
				}
				bsize_precomp[i][j] = best;
				continue;
			}
			bsize_precomp[i][j] = bsize_precomp[i][j-1];
			int r = bsize*i;
			for (int k = bsize*j; k < bsize*(j+1); k++) {
				bsize_precomp[i][j] = max(bsize_precomp[i][j], mxdif_l(k, r));
			}
		}
	}
	cin >> q;
	for (int i = 0; i < q; i++) {
		int x, y; cin >> x >> y; x--; y--;
		int best = -1;
		int lv = (x-1)/bsize+1;
		if (x == 0) lv = 0;
		int rv = (y+1)/bsize-1;
		if (lv > rv) {
			for (int k = x+1; k <= y; k++) {
				best = max(best, mxdif_l(k, x));
			}
			cout << best << "\n";
			continue;
		}
		best = bsize_precomp[lv][rv];
		for (int k = x; k < lv*bsize; k++) {
			best = max(best, mxdif_r(k, y));
		}
		for (int k = y; k >= (rv+1)*bsize; k--) {
			best = max(best, mxdif_l(k, x));
		}
		cout << best << "\n";
	}
}

• Subtask 1: 2 / 2
• Subtask 2: 0 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 65