oj.uz

Submission #604291

# Submission time Handle Problem Language Result Execution time Memory
604291 2022-07-25T03:02:06 Z GusterGoose27 Two Antennas (JOI19_antennas) C++11
24 / 100
 3000 ms 453528 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9740 KB Output is correct
2 Correct 7 ms 10032 KB Output is correct
3 Correct 7 ms 9952 KB Output is correct
4 Correct 7 ms 9900 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 7 ms 9940 KB Output is correct
7 Correct 7 ms 9916 KB Output is correct
8 Correct 7 ms 9940 KB Output is correct
9 Correct 8 ms 9840 KB Output is correct
10 Correct 7 ms 9940 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 7 ms 10024 KB Output is correct
13 Correct 7 ms 9908 KB Output is correct
14 Correct 7 ms 9940 KB Output is correct
15 Correct 8 ms 9932 KB Output is correct
16 Correct 7 ms 10000 KB Output is correct
17 Correct 7 ms 9940 KB Output is correct
18 Correct 7 ms 9940 KB Output is correct
19 Correct 6 ms 9940 KB Output is correct
20 Correct 6 ms 9940 KB Output is correct
21 Correct 6 ms 9940 KB Output is correct
22 Correct 7 ms 10068 KB Output is correct
23 Correct 7 ms 9940 KB Output is correct
24 Correct 7 ms 9940 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9740 KB Output is correct
2 Correct 7 ms 10032 KB Output is correct
3 Correct 7 ms 9952 KB Output is correct
4 Correct 7 ms 9900 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 7 ms 9940 KB Output is correct
7 Correct 7 ms 9916 KB Output is correct
8 Correct 7 ms 9940 KB Output is correct
9 Correct 8 ms 9840 KB Output is correct
10 Correct 7 ms 9940 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 7 ms 10024 KB Output is correct
13 Correct 7 ms 9908 KB Output is correct
14 Correct 7 ms 9940 KB Output is correct
15 Correct 8 ms 9932 KB Output is correct
16 Correct 7 ms 10000 KB Output is correct
17 Correct 7 ms 9940 KB Output is correct
18 Correct 7 ms 9940 KB Output is correct
19 Correct 6 ms 9940 KB Output is correct
20 Correct 6 ms 9940 KB Output is correct
21 Correct 6 ms 9940 KB Output is correct
22 Correct 7 ms 10068 KB Output is correct
23 Correct 7 ms 9940 KB Output is correct
24 Correct 7 ms 9940 KB Output is correct
25 Correct 2190 ms 11900 KB Output is correct
26 Correct 567 ms 11916 KB Output is correct
27 Execution timed out 3079 ms 12460 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 788 ms 289240 KB Output is correct
2 Correct 930 ms 326488 KB Output is correct
3 Correct 552 ms 226724 KB Output is correct
4 Correct 840 ms 326528 KB Output is correct
5 Correct 301 ms 148396 KB Output is correct
6 Correct 773 ms 325628 KB Output is correct
7 Correct 660 ms 281940 KB Output is correct
8 Correct 821 ms 326772 KB Output is correct
9 Correct 93 ms 53652 KB Output is correct
10 Correct 758 ms 327396 KB Output is correct
11 Correct 477 ms 202040 KB Output is correct
12 Correct 748 ms 326888 KB Output is correct
13 Correct 497 ms 435252 KB Output is correct
14 Correct 472 ms 397240 KB Output is correct
15 Correct 459 ms 391684 KB Output is correct
16 Correct 409 ms 373964 KB Output is correct
17 Correct 510 ms 453528 KB Output is correct
18 Correct 452 ms 405452 KB Output is correct
19 Correct 485 ms 428928 KB Output is correct
20 Correct 504 ms 410272 KB Output is correct
21 Correct 446 ms 386712 KB Output is correct
22 Correct 472 ms 406300 KB Output is correct
23 Correct 471 ms 414084 KB Output is correct
24 Correct 442 ms 375572 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9740 KB Output is correct
2 Correct 7 ms 10032 KB Output is correct
3 Correct 7 ms 9952 KB Output is correct
4 Correct 7 ms 9900 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 7 ms 9940 KB Output is correct
7 Correct 7 ms 9916 KB Output is correct
8 Correct 7 ms 9940 KB Output is correct
9 Correct 8 ms 9840 KB Output is correct
10 Correct 7 ms 9940 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 7 ms 10024 KB Output is correct
13 Correct 7 ms 9908 KB Output is correct
14 Correct 7 ms 9940 KB Output is correct
15 Correct 8 ms 9932 KB Output is correct
16 Correct 7 ms 10000 KB Output is correct
17 Correct 7 ms 9940 KB Output is correct
18 Correct 7 ms 9940 KB Output is correct
19 Correct 6 ms 9940 KB Output is correct
20 Correct 6 ms 9940 KB Output is correct
21 Correct 6 ms 9940 KB Output is correct
22 Correct 7 ms 10068 KB Output is correct
23 Correct 7 ms 9940 KB Output is correct
24 Correct 7 ms 9940 KB Output is correct
25 Correct 2190 ms 11900 KB Output is correct
26 Correct 567 ms 11916 KB Output is correct
27 Execution timed out 3079 ms 12460 KB Time limit exceeded
28 Halted 0 ms 0 KB -