제출 #604305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
604305		GusterGoose27	Two Antennas (JOI19_antennas)	C++11	2 / 100	608 ms	418924 KiB

antennas

#pragma GCC optimize("Ofast")
#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 = 447;
const int MAX_blocks = 447;
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
vector<pii> lqueries[MAXN];
vector<pii> rqueries[MAXN];
vector<pii> lans[MAXN];
vector<pii> rans[MAXN];
pii act_queries[MAXN];
int t1[MAXN];
int t2[MAXN];
int bsize_precomp[MAX_blocks][MAX_blocks];
int num_blocks = 0;
bool f = 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));
	}
	void update(int p) {
		if (lp > p || rp < p) return;
		if (lp == p && rp == p) {
			if (active[p]) {
				mn = height[lp];
				mx = height[lp];
			}
			else {
				mn = inf;
				mx = 0;
			}
			return;
		}
		l->update(p);
		r->update(p);
		mn = min(l->mn, r->mn);
		mx = max(l->mx, r->mx);
	}
};

int mxdif_l(int i, int r) {
	if (r > i-valid_dists[i].first) return -1;
	pii p = lans[i][t1[i]++];
	return max(height[i]-p.first, p.second-height[i]);
}

int mxdif_r(int i, int l) {
	if (l < i+valid_dists[i].first) return -1;
	pii p = rans[i][t2[i]++];
	return max(height[i]-p.first, p.second-height[i]);
}

void make_ldif(int i, int r) {
	if (r > i-valid_dists[i].first) return;
	lqueries[i].emplace_back(pii(max(r, i-valid_dists[i].second), i-valid_dists[i].first));
}

void make_rdif(int i, int l) {
	if (l < i+valid_dists[i].first) return;
	rqueries[i].emplace_back(pii(i+valid_dists[i].first, min(l, i+valid_dists[i].second)));
}

void solve() {
	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++) {
					if (f) best = max(best, mxdif_l(k, r));
					else make_ldif(k, r);
				}
				if (f) bsize_precomp[i][j] = best;
				continue;
			}
			if (f) bsize_precomp[i][j] = bsize_precomp[i][j-1];
			int r = bsize*i;
			for (int k = bsize*j; k < bsize*(j+1); k++) {
				if (f) bsize_precomp[i][j] = max(bsize_precomp[i][j], mxdif_l(k, r));
				else make_ldif(k, r);
			}
		}
	}
	for (int i = 0; i < q; i++) {
		int x = act_queries[i].first;
		int y = act_queries[i].second;
		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++) {
				if (f) best = max(best, mxdif_l(k, x));
				else make_ldif(k, x);
			}
			if (f) cout << best << "\n";
			continue;
		}
		if (f) best = bsize_precomp[lv][rv];
		for (int k = x; k < lv*bsize; k++) {
			if (f) best = max(best, mxdif_r(k, y));
			else make_rdif(k, y);
		}
		for (int k = y; k >= (rv+1)*bsize; k--) {
			if (best) best = max(best, mxdif_l(k, x));
			else make_ldif(k, x);
		}
		if (f) cout << best << "\n";
	}
}

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);
	}
	cin >> q;
	for (int i = 0; i < q; i++) {
		int x, y; cin >> x >> y; x--; y--;
		act_queries[i] = pii(x, y);
	}
	solve();
	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->update(v);
		}
		lans[i].resize(lqueries[i].size());
		int t = 0;
		for (pii query: lqueries[i]) {
			lans[i][t++] = cur_tree->diff_in_range(query.first, query.second);
		}
	}
	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->update(v);
		}
		rans[i].resize(rqueries[i].size());
		int t = 0;
		for (pii query: rqueries[i]) {
			rans[i][t++] = cur_tree->diff_in_range(query.first, query.second);
		}
	}
	f = 1;
	solve();
}

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