oj.uz

답안 #917353

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
917353 2024-01-27T23:08:55 Z amirhoseinfar1385 Two Antennas (JOI19_antennas) C++17
22 / 100
 209 ms 42680 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){
		calr(i);
		if(l>r||l>tr||r<tl||tl>tr){
			return -1;
		}
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 37468 KB Output is correct
2 Incorrect 10 ms 37468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 37468 KB Output is correct
2 Incorrect 10 ms 37468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 186 ms 42248 KB Output is correct
2 Correct 205 ms 41712 KB Output is correct
3 Correct 135 ms 42580 KB Output is correct
4 Correct 196 ms 41552 KB Output is correct
5 Correct 103 ms 41936 KB Output is correct
6 Correct 191 ms 41552 KB Output is correct
7 Correct 208 ms 42320 KB Output is correct
8 Correct 183 ms 41548 KB Output is correct
9 Correct 43 ms 38964 KB Output is correct
10 Correct 179 ms 41556 KB Output is correct
11 Correct 135 ms 42680 KB Output is correct
12 Correct 209 ms 41680 KB Output is correct
13 Correct 133 ms 39204 KB Output is correct
14 Correct 130 ms 39420 KB Output is correct
15 Correct 126 ms 39344 KB Output is correct
16 Correct 139 ms 39868 KB Output is correct
17 Correct 143 ms 39424 KB Output is correct
18 Correct 139 ms 39924 KB Output is correct
19 Correct 135 ms 39404 KB Output is correct
20 Correct 127 ms 39412 KB Output is correct
21 Correct 116 ms 39480 KB Output is correct
22 Correct 135 ms 39504 KB Output is correct
23 Correct 127 ms 39372 KB Output is correct
24 Correct 136 ms 39360 KB Output is correct

Subtask #4
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 37468 KB Output is correct
2 Incorrect 10 ms 37468 KB Output isn't correct
3 Halted 0 ms 0 KB -