oj.uz

Submission #614128

# Submission time Handle Problem Language Result Execution time Memory
614128 2022-07-30T19:25:44 Z amunduzbaev Two Antennas (JOI19_antennas) C++17
100 / 100
 754 ms 55608 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef long long ll;
#define int ll
#define sow cerr<<"here"<<endl;

const int N = 2e5 + 5;
const int inf = 2e9;
struct ST{
	int tree[N << 2], mx[N << 2];
	int cost[N << 2];
	
	void init(){
		memset(tree, 1, sizeof tree);
		memset(cost, -1, sizeof cost);
		memset(mx, 0, sizeof mx);
	}
	
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		mx[x << 1] = max(mx[x << 1], mx[x]);
		mx[x << 1 | 1] = max(mx[x << 1 | 1], mx[x]);
		cost[x << 1] = max(cost[x << 1], mx[x << 1] - tree[x << 1]);
		cost[x << 1 | 1] = max(cost[x << 1 | 1], mx[x << 1 | 1] - tree[x << 1 | 1]);
		mx[x] = 0;
	}
	
	void set(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx){
			tree[x] = v, mx[x] = 0;
			return;
		} int m = (lx + rx) >> 1;
		push(x, lx, rx);
		if(i <= m) set(i, v, lx, m, x << 1);
		else set(i, v, m + 1, rx, x << 1 | 1);
		tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
		cost[x] = max(cost[x << 1], cost[x << 1 | 1]);
	}
		
	void add(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			mx[x] = max(mx[x], v);
			cost[x] = max(cost[x], mx[x] - tree[x]);
			return;
		} int m = (lx + rx) >> 1;
		push(x, lx, rx);
		add(l, r, v, lx, m, x << 1);
		add(l, r, v, m + 1, rx, x << 1 | 1);
		cost[x] = max(cost[x << 1], cost[x << 1 | 1]);
	}
	
	int get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -inf;
		if(lx >= l && rx <= r){
			//~ cout<<lx<<" "<<rx<<" "<<cost[x]<<endl;
			return cost[x];
		} int m = (lx + rx) >> 1;
		push(x, lx, rx);
		return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
	}
}tree; 

int h[N], a[N], b[N];
int l[N], r[N], res[N];
vector<ar<int, 2>> Q[N];
int n, q;
int mx[N], mn[N];
int cost[N];

/*

5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
1
1 2

*/

void solve(){
	tree.init();
	vector<int> p(q); iota(p.begin(), p.end(), 0);
	sort(p.begin(), p.end(), [&](int i, int j){
		return r[i] < r[j];
	});
	
	memset(cost, -1, sizeof cost);
	//~ auto set = [&](int i, int v){
		//~ mn[i] = v, mx[i] = 0;
	//~ };
	for(int i=0;i<n;i++){
		tree.set(i, inf);
		//~ set(i, inf);
	}
	//~ auto add = [&](int l, int r, int v){
		//~ for(int i=l;i<=r;i++){
			//~ mx[i] = max(mx[i], v);
			//~ cost[i] = max(cost[i], mx[i] - mn[i]);
		//~ }
	//~ };
	//~ auto get = [&](int l, int r){
		//~ int res = 0;
		//~ for(int i=l;i<=r;i++){
			//~ res = max(res, cost[i]);
		//~ }
		//~ return res;
	//~ };
	
	int j = 0;
	for(int i=0;i<n;i++){
		for(auto [j, t] : Q[i]){
			if(t){
				tree.set(j, h[j]);
			} else {
				tree.set(j, inf);
			}
		} Q[i].clear();
		
		int L = max(i - b[i], 0ll), R = i - a[i];
		if(L <= R){
			tree.add(L, R, h[i]);
		}
		Q[min(i + a[i], n)].push_back({i, 1});
		Q[min(i + b[i] + 1, n)].push_back({i, 0});
		
		while(j < q && r[p[j]] == i){
			res[p[j]] = max(res[p[j]], tree.get(l[p[j]], r[p[j]]));
			j++;
		}
	} Q[n].clear();
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	//~ freopen("in.txt", "r", stdin);
	//~ freopen("out.txt", "r", stdin);
	cin >> n;
	for(int i=0;i<n;i++) cin >> h[i] >> a[i] >> b[i];
	cin >> q;
	for(int i=0;i<q;i++){
		cin >> l[i] >> r[i];
		l[i]--, r[i]--;
	}
	memset(res, -1, sizeof res);
	solve();
	reverse(h, h + n);
	reverse(a, a + n);
	reverse(b, b + n);
	for(int i=0;i<q;i++) l[i] = n - l[i] - 1, r[i] = n - r[i] - 1, swap(l[i], r[i]);
	solve();
	for(int i=0;i<q;i++) cout<<res[i]<<"\n";
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26964 KB Output is correct
2 Correct 17 ms 26916 KB Output is correct
3 Correct 15 ms 26920 KB Output is correct
4 Correct 18 ms 26980 KB Output is correct
5 Correct 15 ms 26964 KB Output is correct
6 Correct 14 ms 26924 KB Output is correct
7 Correct 16 ms 26924 KB Output is correct
8 Correct 15 ms 26924 KB Output is correct
9 Correct 18 ms 26920 KB Output is correct
10 Correct 18 ms 26964 KB Output is correct
11 Correct 18 ms 26992 KB Output is correct
12 Correct 15 ms 27008 KB Output is correct
13 Correct 15 ms 26924 KB Output is correct
14 Correct 15 ms 26964 KB Output is correct
15 Correct 16 ms 26964 KB Output is correct
16 Correct 15 ms 26964 KB Output is correct
17 Correct 16 ms 26928 KB Output is correct
18 Correct 15 ms 26924 KB Output is correct
19 Correct 15 ms 26884 KB Output is correct
20 Correct 18 ms 26964 KB Output is correct
21 Correct 15 ms 26964 KB Output is correct
22 Correct 17 ms 26964 KB Output is correct
23 Correct 14 ms 26980 KB Output is correct
24 Correct 16 ms 27012 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26964 KB Output is correct
2 Correct 17 ms 26916 KB Output is correct
3 Correct 15 ms 26920 KB Output is correct
4 Correct 18 ms 26980 KB Output is correct
5 Correct 15 ms 26964 KB Output is correct
6 Correct 14 ms 26924 KB Output is correct
7 Correct 16 ms 26924 KB Output is correct
8 Correct 15 ms 26924 KB Output is correct
9 Correct 18 ms 26920 KB Output is correct
10 Correct 18 ms 26964 KB Output is correct
11 Correct 18 ms 26992 KB Output is correct
12 Correct 15 ms 27008 KB Output is correct
13 Correct 15 ms 26924 KB Output is correct
14 Correct 15 ms 26964 KB Output is correct
15 Correct 16 ms 26964 KB Output is correct
16 Correct 15 ms 26964 KB Output is correct
17 Correct 16 ms 26928 KB Output is correct
18 Correct 15 ms 26924 KB Output is correct
19 Correct 15 ms 26884 KB Output is correct
20 Correct 18 ms 26964 KB Output is correct
21 Correct 15 ms 26964 KB Output is correct
22 Correct 17 ms 26964 KB Output is correct
23 Correct 14 ms 26980 KB Output is correct
24 Correct 16 ms 27012 KB Output is correct
25 Correct 139 ms 32816 KB Output is correct
26 Correct 28 ms 27712 KB Output is correct
27 Correct 208 ms 35316 KB Output is correct
28 Correct 182 ms 35360 KB Output is correct
29 Correct 134 ms 32832 KB Output is correct
30 Correct 132 ms 32692 KB Output is correct
31 Correct 151 ms 34508 KB Output is correct
32 Correct 180 ms 35348 KB Output is correct
33 Correct 195 ms 34804 KB Output is correct
34 Correct 91 ms 31060 KB Output is correct
35 Correct 194 ms 35164 KB Output is correct
36 Correct 207 ms 35332 KB Output is correct
37 Correct 108 ms 31248 KB Output is correct
38 Correct 183 ms 34500 KB Output is correct
39 Correct 39 ms 28064 KB Output is correct
40 Correct 214 ms 34528 KB Output is correct
41 Correct 132 ms 32396 KB Output is correct
42 Correct 174 ms 34368 KB Output is correct
43 Correct 70 ms 29440 KB Output is correct
44 Correct 190 ms 34332 KB Output is correct
45 Correct 42 ms 28380 KB Output is correct
46 Correct 192 ms 34420 KB Output is correct
47 Correct 56 ms 28984 KB Output is correct
48 Correct 179 ms 34376 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 40176 KB Output is correct
2 Correct 405 ms 41768 KB Output is correct
3 Correct 307 ms 37292 KB Output is correct
4 Correct 414 ms 41648 KB Output is correct
5 Correct 160 ms 33892 KB Output is correct
6 Correct 389 ms 41644 KB Output is correct
7 Correct 377 ms 39744 KB Output is correct
8 Correct 393 ms 41712 KB Output is correct
9 Correct 60 ms 29308 KB Output is correct
10 Correct 413 ms 41828 KB Output is correct
11 Correct 234 ms 36544 KB Output is correct
12 Correct 431 ms 41600 KB Output is correct
13 Correct 294 ms 43124 KB Output is correct
14 Correct 289 ms 42828 KB Output is correct
15 Correct 253 ms 42376 KB Output is correct
16 Correct 253 ms 42256 KB Output is correct
17 Correct 290 ms 43504 KB Output is correct
18 Correct 275 ms 42272 KB Output is correct
19 Correct 276 ms 42732 KB Output is correct
20 Correct 262 ms 42812 KB Output is correct
21 Correct 264 ms 43248 KB Output is correct
22 Correct 278 ms 42948 KB Output is correct
23 Correct 304 ms 43044 KB Output is correct
24 Correct 249 ms 41500 KB Output is correct

Subtask #4
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26964 KB Output is correct
2 Correct 17 ms 26916 KB Output is correct
3 Correct 15 ms 26920 KB Output is correct
4 Correct 18 ms 26980 KB Output is correct
5 Correct 15 ms 26964 KB Output is correct
6 Correct 14 ms 26924 KB Output is correct
7 Correct 16 ms 26924 KB Output is correct
8 Correct 15 ms 26924 KB Output is correct
9 Correct 18 ms 26920 KB Output is correct
10 Correct 18 ms 26964 KB Output is correct
11 Correct 18 ms 26992 KB Output is correct
12 Correct 15 ms 27008 KB Output is correct
13 Correct 15 ms 26924 KB Output is correct
14 Correct 15 ms 26964 KB Output is correct
15 Correct 16 ms 26964 KB Output is correct
16 Correct 15 ms 26964 KB Output is correct
17 Correct 16 ms 26928 KB Output is correct
18 Correct 15 ms 26924 KB Output is correct
19 Correct 15 ms 26884 KB Output is correct
20 Correct 18 ms 26964 KB Output is correct
21 Correct 15 ms 26964 KB Output is correct
22 Correct 17 ms 26964 KB Output is correct
23 Correct 14 ms 26980 KB Output is correct
24 Correct 16 ms 27012 KB Output is correct
25 Correct 139 ms 32816 KB Output is correct
26 Correct 28 ms 27712 KB Output is correct
27 Correct 208 ms 35316 KB Output is correct
28 Correct 182 ms 35360 KB Output is correct
29 Correct 134 ms 32832 KB Output is correct
30 Correct 132 ms 32692 KB Output is correct
31 Correct 151 ms 34508 KB Output is correct
32 Correct 180 ms 35348 KB Output is correct
33 Correct 195 ms 34804 KB Output is correct
34 Correct 91 ms 31060 KB Output is correct
35 Correct 194 ms 35164 KB Output is correct
36 Correct 207 ms 35332 KB Output is correct
37 Correct 108 ms 31248 KB Output is correct
38 Correct 183 ms 34500 KB Output is correct
39 Correct 39 ms 28064 KB Output is correct
40 Correct 214 ms 34528 KB Output is correct
41 Correct 132 ms 32396 KB Output is correct
42 Correct 174 ms 34368 KB Output is correct
43 Correct 70 ms 29440 KB Output is correct
44 Correct 190 ms 34332 KB Output is correct
45 Correct 42 ms 28380 KB Output is correct
46 Correct 192 ms 34420 KB Output is correct
47 Correct 56 ms 28984 KB Output is correct
48 Correct 179 ms 34376 KB Output is correct
49 Correct 371 ms 40176 KB Output is correct
50 Correct 405 ms 41768 KB Output is correct
51 Correct 307 ms 37292 KB Output is correct
52 Correct 414 ms 41648 KB Output is correct
53 Correct 160 ms 33892 KB Output is correct
54 Correct 389 ms 41644 KB Output is correct
55 Correct 377 ms 39744 KB Output is correct
56 Correct 393 ms 41712 KB Output is correct
57 Correct 60 ms 29308 KB Output is correct
58 Correct 413 ms 41828 KB Output is correct
59 Correct 234 ms 36544 KB Output is correct
60 Correct 431 ms 41600 KB Output is correct
61 Correct 294 ms 43124 KB Output is correct
62 Correct 289 ms 42828 KB Output is correct
63 Correct 253 ms 42376 KB Output is correct
64 Correct 253 ms 42256 KB Output is correct
65 Correct 290 ms 43504 KB Output is correct
66 Correct 275 ms 42272 KB Output is correct
67 Correct 276 ms 42732 KB Output is correct
68 Correct 262 ms 42812 KB Output is correct
69 Correct 264 ms 43248 KB Output is correct
70 Correct 278 ms 42948 KB Output is correct
71 Correct 304 ms 43044 KB Output is correct
72 Correct 249 ms 41500 KB Output is correct
73 Correct 683 ms 51088 KB Output is correct
74 Correct 477 ms 46816 KB Output is correct
75 Correct 588 ms 49516 KB Output is correct
76 Correct 754 ms 55388 KB Output is correct
77 Correct 404 ms 42328 KB Output is correct
78 Correct 637 ms 52244 KB Output is correct
79 Correct 667 ms 52944 KB Output is correct
80 Correct 731 ms 55388 KB Output is correct
81 Correct 278 ms 38600 KB Output is correct
82 Correct 565 ms 50700 KB Output is correct
83 Correct 552 ms 48024 KB Output is correct
84 Correct 714 ms 55504 KB Output is correct
85 Correct 484 ms 52236 KB Output is correct
86 Correct 601 ms 55376 KB Output is correct
87 Correct 293 ms 47912 KB Output is correct
88 Correct 563 ms 54776 KB Output is correct
89 Correct 534 ms 53656 KB Output is correct
90 Correct 612 ms 54864 KB Output is correct
91 Correct 373 ms 49720 KB Output is correct
92 Correct 573 ms 55340 KB Output is correct
93 Correct 316 ms 49144 KB Output is correct
94 Correct 605 ms 55608 KB Output is correct
95 Correct 378 ms 49428 KB Output is correct
96 Correct 579 ms 53888 KB Output is correct