Submission #170774

#	Time	Username	Problem	Language	Result	Execution time	Memory
170774		moonrabbit2	Two Antennas (JOI19_antennas)	C++17	100 / 100	947 ms	33548 KiB

antennas

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int,int> TP;
typedef vector<vector<ll>> mat;
const ll mod=1e9+7;
const int N=2e5+5,INF=1e9+5;
int n,q,h[N],a[N],b[N],qs[N],qe[N],ans[N];
struct node{
	int lazy,mxd,mnh;
	node(){
		lazy=-INF; mxd=-INF; mnh=INF;
	}
};
int ANS=806460109;
struct seg{
	node tree[4*N];
	void pushdown(int nd,int l,int r){
		tree[nd].mxd=max(tree[nd].mxd,tree[nd].lazy-tree[nd].mnh);
		if(l!=r){
			tree[nd<<1].lazy=max(tree[nd<<1].lazy,tree[nd].lazy);
			tree[nd<<1|1].lazy=max(tree[nd<<1|1].lazy,tree[nd].lazy);
		}
		tree[nd].lazy=-INF;
	}
	void upd1(int nd,int l,int r,int s,int e,int v){
		pushdown(nd,l,r);
		if(r<s||e<l) return;
		if(s<=l&&r<=e){
			tree[nd].lazy=v;
			pushdown(nd,l,r);
			return;
		}
		int m=(l+r)>>1;
		upd1(nd<<1,l,m,s,e,v); upd1(nd<<1|1,m+1,r,s,e,v);
		tree[nd].mxd=max(tree[nd<<1].mxd,tree[nd<<1|1].mxd); tree[nd].mnh=min(tree[nd<<1].mnh,tree[nd<<1|1].mnh);
	}
	void upd2(int nd,int l,int r,int x,int v){
		pushdown(nd,l,r);
		if(r<x||x<l) return;
		if(l==r){
			tree[nd].mnh=v;
			return;
		}
		int m=(l+r)>>1;
		upd2(nd<<1,l,m,x,v); upd2(nd<<1|1,m+1,r,x,v);
		tree[nd].mxd=max(tree[nd<<1].mxd,tree[nd<<1|1].mxd); tree[nd].mnh=min(tree[nd<<1].mnh,tree[nd<<1|1].mnh);
	}
	int qry(int nd,int l,int r,int s,int e){
		pushdown(nd,l,r);
		if(r<s||e<l) return -INF;
		if(s<=l&&r<=e) return tree[nd].mxd;
		int m=(l+r)>>1;
		return max(qry(nd<<1,l,m,s,e),qry(nd<<1|1,m+1,r,s,e));
	}
};
void solve(){
	vector<pii> events;
	vector<int> queries[N];
	seg tree;
	for(int i=1;i<=n;i++){
		events.emplace_back(i+a[i],i);
		events.emplace_back(i+b[i]+1,-i);
	}
	for(int i=1;i<=q;i++){
		queries[qe[i]].emplace_back(i);
	}
	sort(events.begin(),events.end());
	for(int i=1,j=0;i<=n;i++){
		while(j<events.size()&&events[j].fi==i){
			int p=events[j].se; j++;
			if(p>0) tree.upd2(1,1,n,p,h[p]);
			else tree.upd2(1,1,n,-p,INF);
		}
		if(i-a[i]>=1) tree.upd1(1,1,n,max(1,i-b[i]),i-a[i],h[i]);
		for(auto &it : queries[i]) ans[it]=max(ans[it],tree.qry(1,1,n,qs[it],qe[it]));
	}
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>h[i]>>a[i]>>b[i];
	cin>>q;
	for(int i=1;i<=q;i++){
		cin>>qs[i]>>qe[i];
		ans[i]=-1;
	}
	solve();
	for(int i=1;i<=q;i++){
		qs[i]=n+1-qs[i];
		qe[i]=n+1-qe[i];
		swap(qs[i],qe[i]);
	}
	reverse(h+1,h+1+n); reverse(a+1,a+1+n); reverse(b+1,b+1+n);
	solve();
	for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
	return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'void solve()':
antennas.cpp:76:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j<events.size()&&events[j].fi==i){
         ~^~~~~~~~~~~~~~

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