oj.uz

Submission #604305

# Submission time Handle Problem Language Result Execution time Memory
604305 2022-07-25T03:21:39 Z GusterGoose27 Two Antennas (JOI19_antennas) C++11
2 / 100
 608 ms 418924 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28500 KB Output is correct
2 Correct 16 ms 28656 KB Output is correct
3 Correct 19 ms 28632 KB Output is correct
4 Correct 16 ms 28680 KB Output is correct
5 Correct 16 ms 28628 KB Output is correct
6 Correct 18 ms 28688 KB Output is correct
7 Correct 20 ms 28628 KB Output is correct
8 Correct 17 ms 28688 KB Output is correct
9 Correct 16 ms 28608 KB Output is correct
10 Correct 17 ms 28628 KB Output is correct
11 Correct 16 ms 28500 KB Output is correct
12 Correct 18 ms 28628 KB Output is correct
13 Correct 16 ms 28660 KB Output is correct
14 Correct 16 ms 28628 KB Output is correct
15 Correct 17 ms 28628 KB Output is correct
16 Correct 17 ms 28648 KB Output is correct
17 Correct 16 ms 28604 KB Output is correct
18 Correct 16 ms 28548 KB Output is correct
19 Correct 15 ms 28524 KB Output is correct
20 Correct 16 ms 28604 KB Output is correct
21 Correct 16 ms 28572 KB Output is correct
22 Correct 16 ms 28624 KB Output is correct
23 Correct 17 ms 28628 KB Output is correct
24 Correct 16 ms 28580 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28500 KB Output is correct
2 Correct 16 ms 28656 KB Output is correct
3 Correct 19 ms 28632 KB Output is correct
4 Correct 16 ms 28680 KB Output is correct
5 Correct 16 ms 28628 KB Output is correct
6 Correct 18 ms 28688 KB Output is correct
7 Correct 20 ms 28628 KB Output is correct
8 Correct 17 ms 28688 KB Output is correct
9 Correct 16 ms 28608 KB Output is correct
10 Correct 17 ms 28628 KB Output is correct
11 Correct 16 ms 28500 KB Output is correct
12 Correct 18 ms 28628 KB Output is correct
13 Correct 16 ms 28660 KB Output is correct
14 Correct 16 ms 28628 KB Output is correct
15 Correct 17 ms 28628 KB Output is correct
16 Correct 17 ms 28648 KB Output is correct
17 Correct 16 ms 28604 KB Output is correct
18 Correct 16 ms 28548 KB Output is correct
19 Correct 15 ms 28524 KB Output is correct
20 Correct 16 ms 28604 KB Output is correct
21 Correct 16 ms 28572 KB Output is correct
22 Correct 16 ms 28624 KB Output is correct
23 Correct 17 ms 28628 KB Output is correct
24 Correct 16 ms 28580 KB Output is correct
25 Runtime error 62 ms 60236 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 608 ms 418924 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28500 KB Output is correct
2 Correct 16 ms 28656 KB Output is correct
3 Correct 19 ms 28632 KB Output is correct
4 Correct 16 ms 28680 KB Output is correct
5 Correct 16 ms 28628 KB Output is correct
6 Correct 18 ms 28688 KB Output is correct
7 Correct 20 ms 28628 KB Output is correct
8 Correct 17 ms 28688 KB Output is correct
9 Correct 16 ms 28608 KB Output is correct
10 Correct 17 ms 28628 KB Output is correct
11 Correct 16 ms 28500 KB Output is correct
12 Correct 18 ms 28628 KB Output is correct
13 Correct 16 ms 28660 KB Output is correct
14 Correct 16 ms 28628 KB Output is correct
15 Correct 17 ms 28628 KB Output is correct
16 Correct 17 ms 28648 KB Output is correct
17 Correct 16 ms 28604 KB Output is correct
18 Correct 16 ms 28548 KB Output is correct
19 Correct 15 ms 28524 KB Output is correct
20 Correct 16 ms 28604 KB Output is correct
21 Correct 16 ms 28572 KB Output is correct
22 Correct 16 ms 28624 KB Output is correct
23 Correct 17 ms 28628 KB Output is correct
24 Correct 16 ms 28580 KB Output is correct
25 Runtime error 62 ms 60236 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -