Submission #959786

#	Time	Username	Problem	Language	Result	Execution time	Memory
959786		pcc	Two Antennas (JOI19_antennas)	C++17	100 / 100	856 ms	69368 KiB

antennas

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define int ll

const int mxn = 2e5+10;
const ll inf = 2e9+10;

#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
struct SEG1{
	struct node{
		int mn,mx,val;
		node(){
			mn = inf,mx = -inf,val = -1;
		}
	};
	node seg[mxn*4];
	SEG1(){}
	node pull(node a,node b){
		node re;
		re.mn = min(a.mn,b.mn);
		re.mx = -inf;
		re.val = max(a.val,b.val);
		return re;
	}
	void push(int now,int l,int r){
		seg[ls].mx = max(seg[ls].mx,seg[now].mx);
		seg[rs].mx = max(seg[rs].mx,seg[now].mx);
		seg[ls].val = max(seg[ls].val,seg[ls].mx-seg[ls].mn);
		seg[rs].val = max(seg[rs].val,seg[rs].mx-seg[rs].mn);
		seg[now].mx = -inf;
		return;
	}
	void chmax(int now,int l,int r,int s,int e,int v){
		if(l>=s&&e>=r){
			seg[now].mx = max(seg[now].mx,v);
			seg[now].val = max(seg[now].val,seg[now].mx-seg[now].mn);
			return;
		}
		push(now,l,r);
		if(mid>=s)chmax(ls,l,mid,s,e,v);
		if(mid<e)chmax(rs,mid+1,r,s,e,v);
		seg[now].mn = min(seg[ls].mn,seg[rs].mn);
		seg[now].val = max(seg[ls].val,seg[rs].val);
		return;
	}
	void chmin(int now,int l,int r,int p,int v){
		if(l == r){
			seg[now].mn = v;seg[now].mx = -inf;
			seg[now].val = seg[now].mx-seg[now].mn;
			return;
		}
		push(now,l,r);
		if(mid>=p)chmin(ls,l,mid,p,v);
		else chmin(rs,mid+1,r,p,v);
		seg[now] = pull(seg[ls],seg[rs]);
		return;
	}
	node getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now];
		push(now,l,r);
		if(mid>=e)return getval(ls,l,mid,s,e);
		else if(mid<s)return getval(rs,mid+1,r,s,e);
		else return pull(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
	}
	void init(){
		for(auto &i:seg)i.mn = inf,i.mx = -inf,i.val = -1;
		return;
	}
};

struct SEG2{
	int seg[mxn*4];
	SEG2(){
		for(auto &i:seg)i = -1;
	}
	void modify(int now,int l,int r,int p,int v){
		if(l == r){
			seg[now] = max(seg[now],v);
			return;
		}
		if(mid>=p)modify(ls,l,mid,p,v);
		else modify(rs,mid+1,r,p,v);
		seg[now] = max(seg[ls],seg[rs]);
		return;
	}
	int getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now];
		if(mid>=e)return getval(ls,l,mid,s,e);
		else if(mid<s)return getval(rs,mid+1,r,s,e);
		else return max(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
	}
	void init(){
		for(auto &i:seg)i = -1;
		return;
	}
};

#undef ls
#undef rs
#undef mid

struct D{
	int tp,id,pos;
	D(){}
	D(int tt,int ii,int pp):tp(tt),id(ii),pos(pp){}
	bool operator<(D b)const{
		return pos == b.pos?tp<b.tp:pos<b.pos;
	}
};


SEG1 seg1;
SEG2 seg2;
pii req[mxn];
pii range[mxn];
int H[mxn];
int N,Q;
vector<D> op;
int ans[mxn];

void solve(){
	op.clear();
	seg1.init();
	seg2.init();
	for(int i = 1;i<=N;i++){
		int pl = i+range[i].fs,pr = i+range[i].sc+1;
		pl = min(pl,N),pr = min(pr,N+1);
		op.push_back(D(1,i,pr));
		op.push_back(D(2,i,pl));
		op.push_back(D(3,i,i));
	}
	for(int i = 1;i<=Q;i++){
		op.push_back(D(4,i,req[i].sc));
	}
	sort(op.begin(),op.end());
	for(auto &[tp,id,___]:op){
		//cout<<tp<<':'<<id<<' '<<___<<"::"<<seg1.seg[0].val<<endl;
		if(tp == 1){
			seg2.modify(0,0,N,id,seg1.getval(0,0,N,id,id).val);
			seg1.chmin(0,0,N,id,inf);
		}
		else if(tp == 2){
			seg1.chmin(0,0,N,id,H[id]);
		}
		else if(tp == 3){
			int pl = id-range[id].sc,pr = id-range[id].fs;
			pl = max(pl,0ll),pr = max(pr,0ll);
			seg1.chmax(0,0,N,pl,pr,H[id]);
		}
		else{
			ans[id] = max({ans[id],seg1.getval(0,0,N,req[id].fs,req[id].sc).val,seg2.getval(0,0,N,req[id].fs,req[id].sc)});
		}
	}
	//cout<<endl;
	return;
}

namespace SMALL{
	vector<pii> v[mxn];
	bool peko(int a,int b){
		pii r1 = pii(a+range[a].fs,a+range[a].sc);
		pii r2 = pii(b-range[b].sc,b-range[b].fs);
		if(r1.fs<=b&&b<=r1.sc&&r2.fs<=a&&a<=r2.sc)return true;
		return false;
	}
	void GO(){
		for(int i = 1;i<=N;i++){
			for(int j = i+1;j<=N;j++){
				if(peko(i,j))v[j].push_back(pii(0,i));
			}
		}
		for(int i = 1;i<=Q;i++){
			v[req[i].sc].push_back(pii(1,i));
		}
		memset(ans,-1,sizeof(ans));
		seg2.init();
		for(int i = 1;i<=N;i++){
			for(auto &j:v[i]){
				if(j.fs == 0){
					seg2.modify(0,0,N,j.sc,abs(H[j.sc]-H[i]));
				}
				else{
					ans[j.sc] = seg2.getval(0,0,N,req[j.sc].fs,req[j.sc].sc);
				}
			}
		}
		for(int i = 1;i<=Q;i++)cout<<ans[i]<<'\n';
		return;
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i = 1;i<=N;i++){
		cin>>H[i]>>range[i].fs>>range[i].sc;
	}
	cin>>Q;
	for(int i = 1;i<=Q;i++){
		cin>>req[i].fs>>req[i].sc;
	}
	if(N<=2000){
		SMALL::GO();
		return 0;
	}
	memset(ans,-1,sizeof(ans));
	solve();
	reverse(H+1,H+N+1);
	reverse(range+1,range+N+1);
	for(int i = 1;i<=Q;i++){
		req[i].fs = N+1-req[i].fs,req[i].sc = N+1-req[i].sc;
		swap(req[i].fs,req[i].sc);
	}
	solve();
	for(int i = 1;i<=Q;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}

Compilation message (stderr)

antennas.cpp:203:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  203 | main(){
      | ^~~~

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65