Submission #1024826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024826		tolbi	Two Antennas (JOI19_antennas)	C++17	22 / 100	142 ms	21740 KiB

antennas

#include <bits/stdc++.h>
using namespace std;
#define tol(bi) (1LL<<((int)(bi)))
struct SegTreeMax{
	vector<int> segtree;
	SegTreeMax(int n){
		segtree.resize(tol(ceil(log2(n)+1))-1,INT_MIN);
	}
	void update(int node, int val){
		node+=segtree.size()/2;
		segtree[node]=val;
		while (node){
			node=(node-1)/2;
			segtree[node]=max(segtree[node*2+1],segtree[node*2+2]);
		}
	}
	int query(int tl, int tr, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		if (l>=tl && r<=tr) return segtree[node];
		if (l>tr || r<tl) return INT_MIN;
		int mid = l+(r-l)/2;
		int ret = INT_MIN;
		if (mid>=tl) ret=max(ret,query(tl,tr,l,mid,node*2+1));
		if (mid<tr) ret=max(ret,query(tl,tr,mid+1,r,node*2+2));
		return ret;
	}
};
struct SegTreeMin{
	vector<int> segtree;
	SegTreeMin(int n){
		segtree.resize(tol(ceil(log2(n)+1))-1,INT_MAX);
	}
	void update(int node, int val){
		node+=segtree.size()/2;
		segtree[node]=val;
		while (node){
			node=(node-1)/2;
			segtree[node]=min(segtree[node*2+1],segtree[node*2+2]);
		}
	}
	int query(int tl, int tr, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		if (l>=tl && r<=tr) return segtree[node];
		if (l>tr || r<tl) return INT_MAX;
		int mid = l+(r-l)/2;
		int ret = INT_MAX;
		if (mid>=tl) ret=min(ret,query(tl,tr,l,mid,node*2+1));
		if (mid<tr) ret=min(ret,query(tl,tr,mid+1,r,node*2+2));
		return ret;
	}
};
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;cin>>n;
	vector<array<int,3>> arr(n);
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < 3; ++j){
			cin>>arr[i][j];
		}
	}
	vector<vector<pair<int,int>>> rr(n+1);
	for (int i = 0; i < n-1; ++i)
	{
		rr[min(n-1,i+arr[i][1])].push_back({i,1});
		rr[min(n,i+arr[i][2]+1)].push_back({i,-1});
	}
	int q;cin>>q;
	SegTreeMax segtreema(n);
	SegTreeMin segtreemi(n);
	while (q--){
		int l,r;cin>>l>>r;
		int ans = -1;
		for (int i = 0; i < n; i++){
			for (auto it : rr[i]){
				int node = it.first;
				if (it.second==1){
					segtreema.update(node,arr[node][0]);
					segtreemi.update(node,arr[node][0]);
				}
				else {
					segtreema.update(node,INT_MIN);
					segtreemi.update(node,INT_MAX);
				}
			}
			if (i<=r-1){
				int mava = segtreema.query(max(l-1,i-arr[i][2]),i-arr[i][1]);
				int miva = segtreemi.query(max(l-1,i-arr[i][2]),i-arr[i][1]);
				if (mava!=INT_MIN){
					ans=max(ans,abs(mava-arr[i][0]));
				}
				if (miva!=INT_MAX){
					ans=max(ans,abs(arr[i][0]-miva));
				}
			}
		}
		cout<<ans<<endl;
		for (int i = 0; i < n; ++i)
		{
			segtreemi.update(i,INT_MAX);
			segtreema.update(i,INT_MIN);
		}
	}
}

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