oj.uz

Submission #917348

# Submission time Handle Problem Language Result Execution time Memory
917348 2024-01-27T23:02:39 Z amirhoseinfar1385 Two Antennas (JOI19_antennas) C++17
100 / 100
 429 ms 79696 KB 
#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10;
long long n,q;
long long h[maxn],a[maxn],b[maxn];
long long kaf=(1<<19),inf=1e15;
vector<long long>del[maxn],ins[maxn];
vector<pair<long long,long long>>allq[maxn];
long long res[maxn];
struct segment{
	struct node{
		long long r,mxq,mnq,mx,mn;
		node(){
			r=-1;
			mxq=mx=-inf;
			mn=mnq=inf;
		}
	};
	void calr(long long i){
		seg[i].r=max(seg[i].r,seg[i].mxq-seg[i].mn);
		seg[i].r=max(seg[i].r,seg[i].mx-seg[i].mnq);
	}
	void calc(long long i){
		calr(i);
		if(i>=kaf){
			return ;
		}
		seg[i].r=max(seg[i].r,max(seg[(i<<1)].r,seg[(i<<1)^1].r));
		seg[i].mx=max(seg[(i<<1)].mx,seg[(i<<1)^1].mx);
		seg[i].mn=min(seg[(i<<1)].mn,seg[(i<<1)^1].mn);
	}

	void shift(long long i){
		if(i>=kaf){
			return ;
		}
		seg[(i<<1)].mxq=max(seg[(i<<1)].mxq,seg[i].mxq);
		seg[(i<<1)].mnq=min(seg[(i<<1)].mnq,seg[i].mnq);
		seg[(i<<1)^1].mxq=max(seg[(i<<1)^1].mxq,seg[i].mxq);
		seg[(i<<1)^1].mnq=min(seg[(i<<1)^1].mnq,seg[i].mnq);
		seg[i].mxq=-inf;
		seg[i].mnq=inf;
	}
	node seg[(1<<20)];
	void upd(long long i,long long l,long long r,long long tl,long long tr,long long mx,long long mn){
		calr(i);
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			calr(i);
			seg[i].mxq=-inf;
			seg[i].mnq=inf;
			seg[i].mx=mx;
			seg[i].mn=mn;
			return ;
		}
		shift(i);
		long long m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,mx,mn);
		upd((i<<1)^1,m+1,r,tl,tr,mx,mn);
		calc(i);
		return ;
	}
	void qu(long long i,long long l,long long r,long long tl,long long tr,long long w){
		calr(i);
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i].mnq=min(seg[i].mnq,w);
			seg[i].mxq=max(seg[i].mxq,w);
			calr(i);
			return ;
		}
		long long m=(l+r)>>1;
		qu((i<<1),l,m,tl,tr,w);
		qu((i<<1)^1,m+1,r,tl,tr,w);
		calc(i);
	}
	long long pors(long long i,long long l,long long r,long long tl,long long tr){
		calr(i);
		if(l>r||l>tr||r<tl||tl>tr){
			return -1;
		}
		if(l>=tl&&r<=tr){
			return seg[i].r;
		}
		shift(i);
		long long m=(l+r)>>1;
		return max(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));	
	}
}seg;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(long long i=1;i<=n;i++){
		cin>>h[i]>>a[i]>>b[i];
		if(a[i]+i<maxn){
			ins[i+a[i]].push_back(i);
		}
		if(b[i]+i+1<maxn){
			del[b[i]+i+1].push_back(i);
		}
	}
	cin>>q;
	for(long long i=0;i<q;i++){
		long long l,r;
		cin>>l>>r;
		allq[r].push_back(make_pair(l,i));
	}
	for(long long i=1;i<=n;i++){
		for(auto x:del[i]){
			seg.upd(1,0,kaf-1,x,x,-inf,inf);
		}
		for(auto x:ins[i]){
			seg.upd(1,0,kaf-1,x,x,h[x],h[x]);
		}
		seg.qu(1,0,kaf-1,i-b[i],i-a[i],h[i]);
		for(auto x:allq[i]){
			res[x.second]=seg.pors(1,0,kaf-1,x.first,i);
		}
	}
	for(long long i=0;i<q;i++){
		cout<<res[i]<<"\n";
	}
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 59992 KB Output is correct
2 Correct 13 ms 59996 KB Output is correct
3 Correct 12 ms 59996 KB Output is correct
4 Correct 12 ms 60096 KB Output is correct
5 Correct 11 ms 59996 KB Output is correct
6 Correct 12 ms 60112 KB Output is correct
7 Correct 13 ms 59996 KB Output is correct
8 Correct 12 ms 60144 KB Output is correct
9 Correct 11 ms 59996 KB Output is correct
10 Correct 12 ms 60104 KB Output is correct
11 Correct 12 ms 59992 KB Output is correct
12 Correct 11 ms 59996 KB Output is correct
13 Correct 12 ms 59992 KB Output is correct
14 Correct 12 ms 59996 KB Output is correct
15 Correct 12 ms 59996 KB Output is correct
16 Correct 12 ms 60168 KB Output is correct
17 Correct 12 ms 60148 KB Output is correct
18 Correct 11 ms 59996 KB Output is correct
19 Correct 12 ms 59996 KB Output is correct
20 Correct 13 ms 59996 KB Output is correct
21 Correct 11 ms 60112 KB Output is correct
22 Correct 12 ms 59996 KB Output is correct
23 Correct 13 ms 60096 KB Output is correct
24 Correct 12 ms 60000 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 59992 KB Output is correct
2 Correct 13 ms 59996 KB Output is correct
3 Correct 12 ms 59996 KB Output is correct
4 Correct 12 ms 60096 KB Output is correct
5 Correct 11 ms 59996 KB Output is correct
6 Correct 12 ms 60112 KB Output is correct
7 Correct 13 ms 59996 KB Output is correct
8 Correct 12 ms 60144 KB Output is correct
9 Correct 11 ms 59996 KB Output is correct
10 Correct 12 ms 60104 KB Output is correct
11 Correct 12 ms 59992 KB Output is correct
12 Correct 11 ms 59996 KB Output is correct
13 Correct 12 ms 59992 KB Output is correct
14 Correct 12 ms 59996 KB Output is correct
15 Correct 12 ms 59996 KB Output is correct
16 Correct 12 ms 60168 KB Output is correct
17 Correct 12 ms 60148 KB Output is correct
18 Correct 11 ms 59996 KB Output is correct
19 Correct 12 ms 59996 KB Output is correct
20 Correct 13 ms 59996 KB Output is correct
21 Correct 11 ms 60112 KB Output is correct
22 Correct 12 ms 59996 KB Output is correct
23 Correct 13 ms 60096 KB Output is correct
24 Correct 12 ms 60000 KB Output is correct
25 Correct 79 ms 65876 KB Output is correct
26 Correct 23 ms 60668 KB Output is correct
27 Correct 110 ms 68432 KB Output is correct
28 Correct 112 ms 68544 KB Output is correct
29 Correct 79 ms 65940 KB Output is correct
30 Correct 78 ms 65780 KB Output is correct
31 Correct 96 ms 67408 KB Output is correct
32 Correct 119 ms 68672 KB Output is correct
33 Correct 107 ms 67920 KB Output is correct
34 Correct 60 ms 64080 KB Output is correct
35 Correct 113 ms 68436 KB Output is correct
36 Correct 110 ms 68564 KB Output is correct
37 Correct 70 ms 64424 KB Output is correct
38 Correct 108 ms 67596 KB Output is correct
39 Correct 28 ms 61164 KB Output is correct
40 Correct 112 ms 67604 KB Output is correct
41 Correct 83 ms 65696 KB Output is correct
42 Correct 116 ms 67724 KB Output is correct
43 Correct 48 ms 62548 KB Output is correct
44 Correct 110 ms 67708 KB Output is correct
45 Correct 32 ms 61272 KB Output is correct
46 Correct 109 ms 67668 KB Output is correct
47 Correct 38 ms 62036 KB Output is correct
48 Correct 123 ms 67736 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 69716 KB Output is correct
2 Correct 252 ms 70008 KB Output is correct
3 Correct 206 ms 69104 KB Output is correct
4 Correct 280 ms 70016 KB Output is correct
5 Correct 115 ms 67140 KB Output is correct
6 Correct 238 ms 69996 KB Output is correct
7 Correct 217 ms 69524 KB Output is correct
8 Correct 252 ms 69972 KB Output is correct
9 Correct 44 ms 62296 KB Output is correct
10 Correct 247 ms 70016 KB Output is correct
11 Correct 173 ms 68848 KB Output is correct
12 Correct 235 ms 69972 KB Output is correct
13 Correct 176 ms 68212 KB Output is correct
14 Correct 171 ms 68424 KB Output is correct
15 Correct 162 ms 68168 KB Output is correct
16 Correct 182 ms 68684 KB Output is correct
17 Correct 185 ms 68500 KB Output is correct
18 Correct 199 ms 68696 KB Output is correct
19 Correct 172 ms 68036 KB Output is correct
20 Correct 168 ms 68416 KB Output is correct
21 Correct 150 ms 67976 KB Output is correct
22 Correct 164 ms 68420 KB Output is correct
23 Correct 165 ms 68300 KB Output is correct
24 Correct 190 ms 68312 KB Output is correct

Subtask #4
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 59992 KB Output is correct
2 Correct 13 ms 59996 KB Output is correct
3 Correct 12 ms 59996 KB Output is correct
4 Correct 12 ms 60096 KB Output is correct
5 Correct 11 ms 59996 KB Output is correct
6 Correct 12 ms 60112 KB Output is correct
7 Correct 13 ms 59996 KB Output is correct
8 Correct 12 ms 60144 KB Output is correct
9 Correct 11 ms 59996 KB Output is correct
10 Correct 12 ms 60104 KB Output is correct
11 Correct 12 ms 59992 KB Output is correct
12 Correct 11 ms 59996 KB Output is correct
13 Correct 12 ms 59992 KB Output is correct
14 Correct 12 ms 59996 KB Output is correct
15 Correct 12 ms 59996 KB Output is correct
16 Correct 12 ms 60168 KB Output is correct
17 Correct 12 ms 60148 KB Output is correct
18 Correct 11 ms 59996 KB Output is correct
19 Correct 12 ms 59996 KB Output is correct
20 Correct 13 ms 59996 KB Output is correct
21 Correct 11 ms 60112 KB Output is correct
22 Correct 12 ms 59996 KB Output is correct
23 Correct 13 ms 60096 KB Output is correct
24 Correct 12 ms 60000 KB Output is correct
25 Correct 79 ms 65876 KB Output is correct
26 Correct 23 ms 60668 KB Output is correct
27 Correct 110 ms 68432 KB Output is correct
28 Correct 112 ms 68544 KB Output is correct
29 Correct 79 ms 65940 KB Output is correct
30 Correct 78 ms 65780 KB Output is correct
31 Correct 96 ms 67408 KB Output is correct
32 Correct 119 ms 68672 KB Output is correct
33 Correct 107 ms 67920 KB Output is correct
34 Correct 60 ms 64080 KB Output is correct
35 Correct 113 ms 68436 KB Output is correct
36 Correct 110 ms 68564 KB Output is correct
37 Correct 70 ms 64424 KB Output is correct
38 Correct 108 ms 67596 KB Output is correct
39 Correct 28 ms 61164 KB Output is correct
40 Correct 112 ms 67604 KB Output is correct
41 Correct 83 ms 65696 KB Output is correct
42 Correct 116 ms 67724 KB Output is correct
43 Correct 48 ms 62548 KB Output is correct
44 Correct 110 ms 67708 KB Output is correct
45 Correct 32 ms 61272 KB Output is correct
46 Correct 109 ms 67668 KB Output is correct
47 Correct 38 ms 62036 KB Output is correct
48 Correct 123 ms 67736 KB Output is correct
49 Correct 217 ms 69716 KB Output is correct
50 Correct 252 ms 70008 KB Output is correct
51 Correct 206 ms 69104 KB Output is correct
52 Correct 280 ms 70016 KB Output is correct
53 Correct 115 ms 67140 KB Output is correct
54 Correct 238 ms 69996 KB Output is correct
55 Correct 217 ms 69524 KB Output is correct
56 Correct 252 ms 69972 KB Output is correct
57 Correct 44 ms 62296 KB Output is correct
58 Correct 247 ms 70016 KB Output is correct
59 Correct 173 ms 68848 KB Output is correct
60 Correct 235 ms 69972 KB Output is correct
61 Correct 176 ms 68212 KB Output is correct
62 Correct 171 ms 68424 KB Output is correct
63 Correct 162 ms 68168 KB Output is correct
64 Correct 182 ms 68684 KB Output is correct
65 Correct 185 ms 68500 KB Output is correct
66 Correct 199 ms 68696 KB Output is correct
67 Correct 172 ms 68036 KB Output is correct
68 Correct 168 ms 68416 KB Output is correct
69 Correct 150 ms 67976 KB Output is correct
70 Correct 164 ms 68420 KB Output is correct
71 Correct 165 ms 68300 KB Output is correct
72 Correct 190 ms 68312 KB Output is correct
73 Correct 416 ms 76788 KB Output is correct
74 Correct 254 ms 70640 KB Output is correct
75 Correct 381 ms 78636 KB Output is correct
76 Correct 403 ms 79696 KB Output is correct
77 Correct 242 ms 74068 KB Output is correct
78 Correct 429 ms 76340 KB Output is correct
79 Correct 399 ms 79092 KB Output is correct
80 Correct 426 ms 79696 KB Output is correct
81 Correct 160 ms 71224 KB Output is correct
82 Correct 330 ms 74596 KB Output is correct
83 Correct 348 ms 78156 KB Output is correct
84 Correct 416 ms 79584 KB Output is correct
85 Correct 288 ms 73092 KB Output is correct
86 Correct 361 ms 76916 KB Output is correct
87 Correct 218 ms 69452 KB Output is correct
88 Correct 367 ms 77216 KB Output is correct
89 Correct 319 ms 74808 KB Output is correct
90 Correct 371 ms 77652 KB Output is correct
91 Correct 240 ms 70916 KB Output is correct
92 Correct 339 ms 76860 KB Output is correct
93 Correct 188 ms 69440 KB Output is correct
94 Correct 337 ms 76912 KB Output is correct
95 Correct 234 ms 70400 KB Output is correct
96 Correct 365 ms 77004 KB Output is correct