oj.uz

Submission #917352

# Submission time Handle Problem Language Result Execution time Memory
917352 2024-01-27T23:08:13 Z amirhoseinfar1385 Two Antennas (JOI19_antennas) C++17
22 / 100
 215 ms 42588 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
int n,q;
int h[maxn],a[maxn],b[maxn];
int kaf=(1<<19),inf=1e9+5;
vector<int>del[maxn],ins[maxn];
vector<pair<int,int>>allq[maxn];
int res[maxn];
struct segment{
	struct node{
		int r,mxq,mnq,mx,mn;
		node(){
			r=-1;
			mxq=mx=-inf;
			mn=mnq=inf;
		}
	};
	void calr(int 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(int 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(int 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(int i,int l,int r,int tl,int tr,int mx,int mn){
		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);
		int 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(int i,int l,int r,int tl,int tr,int w){
		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 ;
		}
		int m=(l+r)>>1;
		qu((i<<1),l,m,tl,tr,w);
		qu((i<<1)^1,m+1,r,tl,tr,w);
		calc(i);
	}
	int pors(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return -1;
		}
		calr(i);
		if(l>=tl&&r<=tr){
			return seg[i].r;
		}
		shift(i);
		int 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(int 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(int i=0;i<q;i++){
		int l,r;
		cin>>l>>r;
		allq[r].push_back(make_pair(l,i));
	}
	for(int 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(int i=0;i<q;i++){
		cout<<res[i]<<"\n";
	}
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 37464 KB Output is correct
2 Incorrect 9 ms 37468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 37464 KB Output is correct
2 Incorrect 9 ms 37468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 42080 KB Output is correct
2 Correct 208 ms 41712 KB Output is correct
3 Correct 138 ms 42400 KB Output is correct
4 Correct 199 ms 41556 KB Output is correct
5 Correct 104 ms 41808 KB Output is correct
6 Correct 191 ms 41556 KB Output is correct
7 Correct 173 ms 42064 KB Output is correct
8 Correct 215 ms 41552 KB Output is correct
9 Correct 35 ms 38748 KB Output is correct
10 Correct 195 ms 41552 KB Output is correct
11 Correct 126 ms 42588 KB Output is correct
12 Correct 212 ms 41888 KB Output is correct
13 Correct 133 ms 39200 KB Output is correct
14 Correct 142 ms 39348 KB Output is correct
15 Correct 126 ms 39504 KB Output is correct
16 Correct 150 ms 39764 KB Output is correct
17 Correct 138 ms 39380 KB Output is correct
18 Correct 136 ms 39760 KB Output is correct
19 Correct 140 ms 39236 KB Output is correct
20 Correct 127 ms 39460 KB Output is correct
21 Correct 115 ms 39220 KB Output is correct
22 Correct 124 ms 39532 KB Output is correct
23 Correct 135 ms 39300 KB Output is correct
24 Correct 131 ms 39372 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 37464 KB Output is correct
2 Incorrect 9 ms 37468 KB Output isn't correct
3 Halted 0 ms 0 KB -