Submission #105121

#	Time	Username	Problem	Language	Result	Execution time	Memory
105121		reality	Two Antennas (JOI19_antennas)	C++17	100 / 100	1139 ms	40116 KiB

antennas

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 2e5 + 5;
int n;
int s[N];
int A[N];
int B[N];
int L[N];
int R[N];
int ans[N];
vi Up[N];
vi Qu[N];
const int oo = 1e9;
const pii OO = pii(oo,-oo);
pii operator + (pii a,pii b) {
	return pii(min(a.fi,b.fi),max(a.se,b.se));
}
pii tx[N * 4];
pii llz[N * 4];
int t[N * 4];
void upd(int node) {
	smax(t[node],max(tx[node].se - llz[node].fi,llz[node].se - tx[node].fi));
}
void lz(int l,int r,int node) {
	if (l != r) 
		llz[node * 2] = llz[node * 2] + llz[node],
		llz[node * 2 + 1] = llz[node * 2 + 1] + llz[node];
	upd(node);
	llz[node] = OO;
}
void build(int l,int r,int node) {
	if (l == r) {
		tx[node] = llz[node] = OO;
		t[node] = -2 * oo;
	} else {
		int m = (l + r) / 2;
		build(l,m,node * 2);
		build(m+1,r,node * 2 + 1);
		tx[node] = tx[node * 2] + tx[node * 2 + 1];
		llz[node] = OO;
		t[node] = -2 * oo;
	}
}
void Upy(int l,int r,int l1,int r1,pii v,int node) {
	lz(l,r,node);
	if (l1 <= l && r <= r1)
		llz[node] = v,lz(l,r,node);
	else {
		int m = (l + r) / 2;
		if (l1 <= m)
			Upy(l,m,l1,r1,v,node * 2);
		else
			lz(l,m,node * 2);
		if (m+1<=r1)
			Upy(m+1,r,l1,r1,v,node * 2 + 1);
		else
			lz(m+1,r,node * 2 + 1);
		smax(t[node],t[node * 2]);
		smax(t[node],t[node * 2 + 1]);	
	}
}
void Upx(int l,int r,int ps,pii v,int node) {
	lz(l,r,node);
	if (l == r)
		tx[node] = v;
	else {
		int m = (l + r) / 2;
		if (ps <= m)
			Upx(l,m,ps,v,node * 2);
		else
			lz(l,m,node * 2);
		if (m+1<=ps)
			Upx(m+1,r,ps,v,node * 2 + 1);
		else
			lz(m+1,r,node * 2 + 1);
		tx[node] = tx[node * 2] + tx[node * 2 + 1];
		smax(t[node],t[node * 2]);
		smax(t[node],t[node * 2 + 1]);
	}
}
int query(int l,int r,int l1,int r1,int node) {
	lz(l,r,node);
	if (l1 <= l && r <= r1)
		return t[node];
	int m = (l + r) / 2;
	int ans = -2 * oo;
	if (l1 <= m)
		smax(ans,query(l,m,l1,r1,node * 2));
	if (m+1<=r1)
		smax(ans,query(m+1,r,l1,r1,node * 2 + 1));
	return ans;
}
int main(void) {
    int n,q;
    cin>>n;
    for (int i = 1;i <= n;++i)
    	cin>>s[i]>>A[i]>>B[i];
    cin>>q;
    for (int i = 1;i <= q;++i)
    	cin>>L[i]>>R[i],Qu[R[i]].pb(i);
    build(1,n,1);
    for (int i = 1;i <= n;++i) {
    	const int ly = min(n+1,A[i]+i);
    	const int ry = min(n,i + B[i]);
    	if (ly <= ry)
	    	Up[ly].pb(i),Up[ry + 1].pb(-i);
    }
    for (int i = 1;i <= n;++i) {
    	const int lx = max(1,i - B[i]);
    	const int rx = min(n,i - A[i]);
    	for (auto it : Up[i]) {
    		Upx(1,n,abs(it),it > 0 ? mp(s[it],s[it]) : OO,1);
    	}
    	if (lx <= rx) {
	    	Upy(1,n,lx,rx,mp(s[i],s[i]),1);
    	}
    	for (auto it : Qu[i])
    		ans[it] = query(1,n,L[it],R[it],1);
    }
    for (int i = 1;i <= q;++i)
    	cout << max(-1,ans[i]) << '\n';
    return 0;
}

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