Submission #1024914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024914		tolbi	Two Antennas (JOI19_antennas)	C++17	100 / 100	631 ms	41436 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
#define tol(bi) (1LL<<((int)(bi)))
typedef long long ll;
constexpr int MAXN = 200003;
constexpr ll INF = 1e15;
array<int,3> qu[MAXN];
array<int,3> arr[MAXN];
vector<pair<int,int>> rr[MAXN];
ll ansarr[MAXN];
struct SegTree{
	ll tag1[MAXN*4],tag2[MAXN*4];
	//tag1 subtree min
	//tag2 subtree ans
	//tag3 lazy
	int tag3[MAXN*4], sz;
	SegTree(int n):sz(tol(ceil(log2(n)+1))-1){
		fill(tag1,tag1+sz,INF);
		fill(tag2,tag2+sz,-INF);
		fill(tag3,tag3+sz,0);
	}
	void dallan(int nd){
		if (tag3[nd]){
			tag2[nd]=max(tag2[nd],tag3[nd]-tag1[nd]);
			if (nd*2+1<sz){
				tag3[nd*2+1]=max(tag3[nd*2+1],tag3[nd]);
				tag3[nd*2+2]=max(tag3[nd*2+2],tag3[nd]);
			}
			tag3[nd]=0;
		}
	}
	void upd1(int nd, ll val){
		int l = 0, r = sz/2;
		int node = 0;
		while (l<r){
			dallan(node);
			int mid = l+(r-l)/2;
			if (mid>=nd){
				r=mid;
				node=node*2+1;
			}
			else {
				l=mid+1;
				node=node*2+2;
			}
		}
		dallan(node);
		tag1[node]=val;
		while (node){
			node=(node-1)/2;
			tag1[node]=min(tag1[node*2+1],tag1[node*2+2]);
		}
	}
	void upd2(int tl, int tr, int val, int l = 0, int r = -1, int node = 0){
		dallan(node);
		if (r==-1) r = sz/2;
		if (l>=tl && r<=tr) {
			tag3[node]=max(tag3[node],val);
			dallan(node);
			return;
		}
		if (l>tr || r<tl) return;
		int mid = l+(r-l)/2;
		upd2(tl, tr, val, l, mid, node*2+1);
		upd2(tl, tr, val, mid+1, r, node*2+2);
		tag2[node]=max(tag2[node*2+1],tag2[node*2+2]);
	}
	ll query(int tl, int tr, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = sz/2;
		dallan(node);
		if (l>=tl && r<=tr) return tag2[node];
		if (l>tr || r<tl) return -INF;
		int mid = l+(r-l)/2;
		ll ret = -INF;
		ret=max(ret,query(tl,tr,l,mid,node*2+1));
		ret=max(ret,query(tl,tr,mid+1,r,node*2+2));
		return ret;
	}
};
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	memset(ansarr,-1,sizeof(ansarr));
	int n;cin>>n;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < 3; ++j){
			cin>>arr[i][j];
		}
	}
	int q;cin>>q;
	for (int i = 0; i < q; ++i)
	{
		cin>>qu[i][0]>>qu[i][1];
		qu[i][0]--,qu[i][1]--;
		qu[i][2]=i;
	}
	function<void(void)> solve = [&](void)->void{
		for (int i = 0; i < n-1; ++i)
		{
			if (i+arr[i][1]>=n) continue;
			rr[min(n-1,i+arr[i][1])].push_back({i,1});
			rr[min(n,i+arr[i][2]+1)].push_back({i,-1});
		}
		sort(qu,qu+q,[&](const array<int,3> &a, const array<int,3> &b){
			return a[1]<b[1];
		});
		SegTree segtree(n);
		int ind = 0;
		for (int i = 0; i < n; i++){
			while (rr[i].size()){
				int node = rr[i].back().first;
				int flag = rr[i].back().second;
				rr[i].pop_back();
				if (flag==1){
					segtree.upd1(node,arr[node][0]);
				}
				else {
					segtree.upd1(node,INF);
				}
			}
			segtree.upd2(i-arr[i][2],i-arr[i][1],arr[i][0]);
			while (ind<q && qu[ind][1]==i){
				ansarr[qu[ind][2]]=max(ansarr[qu[ind][2]],segtree.query(qu[ind][0],qu[ind][1]));
				ind++;
			}
		}
	};
	solve();
	reverse(arr, arr+n);
	for (int i = 0; i < q; ++i)
	{
		qu[i][0]=n-qu[i][0]-1;
		qu[i][1]=n-qu[i][1]-1;
		swap(qu[i][0],qu[i][1]);
	}
	solve();
	for (int i = 0; i < q; ++i)
	{
		cout<<ansarr[i]<<endl;
	}
}

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