Submission #1180317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180317		ByeWorld	Two Antennas (JOI19_antennas)	C++20	100 / 100	527 ms	60436 KiB

antennas

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
const int MAXN = 2e5+10;
const int MAXA = 1e9;
const int INF = 1e10+100;
const int SQRT = 450;
const int LOG = 19;
const int MOD = 998244353;
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }
int sum(int a, int b){ a %= MOD; b %= MOD; return (a+b)%MOD; }
void chsum(int &a, int b){ a %= MOD; b %= MOD; a = (a+b)%MOD; }
void chsub(int &a, int b){ a %= MOD; b %= MOD; a = (a+MOD-b)%MOD; }
int mul(int a, int b){ a %= MOD; b %= MOD; return a*b%MOD;}
void chmul(int &a, int b){ a = a*b%MOD; }
int expo(int a, int b){
	if(b==0) return 1;
	int te = expo(a, b/2); te = mul(te, te);
	return (b%2 ? mul(te, a) : te);
}

int n, h[MAXN], a[MAXN], b[MAXN];

struct segtree {
	int st[4*MAXN];
	void bd(int id,int l, int r){
		st[id] = -INF;
		if(l==r) return;
		bd(lf,l,md); bd(rg,md+1,r);
	}
	int que(int id,int l, int r,int x,int y){
		if(x<=l && r<=y) return st[id];
		if(r<x || y<l) return -INF;
		return max(que(lf,l,md,x,y), que(rg,md+1,r,x,y));
	}
	int upd(int id,int l, int r,int x,int y){
		if(l==r && l==x) return st[id] = max(st[id], y);
		if(r<x || x<l) return st[id];
		return st[id] = max(upd(lf,l,md,x,y), upd(rg,md+1,r,x,y));
	}
} ST;
struct node {
	int a=-INF, b=-INF, laz=-INF;
} NOL;
struct seg {
	node st[4*MAXN];
	void bd(int id,int l,int r){
		st[id].a = -INF; st[id].b = -INF; st[id].laz = -INF;
		if(l==r) return;
		bd(lf,l,md); bd(rg,md+1,r);
	}
	node mrg(node a, node b){
		node ret;
		ret.a = max(a.a, b.a); ret.b = max(a.b, b.b);
		return ret;
	}
	void push(int id, int val){
		chmx(st[id].b, st[id].a + val);
		chmx(st[id].laz, val);
	}
	void bnc(int id){
		if(st[id].laz==-INF) return;
		push(lf, st[id].laz); push(rg, st[id].laz);
		st[id].laz = -INF;
	}
	node make(int id,int l, int r,int x,pii y){
		if(l==r && x==l){
			st[id].a = y.fi;
			return st[id];
		}
		if(r<x || x<l) return st[id];
		bnc(id);
		return st[id] = mrg(make(lf,l,md,x,y), make(rg,md+1,r,x,y));
	}
	int que(int id,int l, int r,int x,int y){
		if(x<=l && r<=y) return st[id].b;
		if(r<x || y<l) return -INF;
		bnc(id);
		return max(que(lf,l,md,x,y), que(rg,md+1,r,x,y));
	}
	node upd(int id,int l, int r,int x,int y,int p){
		if(x<=l && r<=y){
			push(id, p);
			return st[id];
		}
		if(r<x || y<l) return st[id];
		bnc(id);
		return st[id] = mrg(upd(lf,l,md,x,y,p), upd(rg,md+1,r,x,y,p));
	}
} X, Y;
vector<int>on[MAXN], off[MAXN];
vector<pii> que[MAXN];
int ans[MAXN];

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1; i<=n; i++){
		cin>>h[i]>>a[i]>>b[i];
		if(i+a[i]<=n) on[i+a[i]].pb(i); 
		if(i+b[i]<=n) off[i+b[i]].pb(i);
	}
	int Q; cin>>Q;
	for(int P=1; P<=Q; P++){
		ans[P] = -1;
		int l, r;cin>>l>>r;
		que[r].pb({l,P});
	}

	ST.bd(1,1,n); X.bd(1,1,n); Y.bd(1,1,n);
	for(int i=1; i<=n; i++){
		// cout << i << " i\n";
		for(auto j : on[i]){ // idx jadi active
			// cout << j << "on\n";
			X.make(1,1,n, j, pii(-h[j],-INF) );
			Y.make(1,1,n, j, pii(h[j],-INF) );
		}
		int l = i-b[i], r = i-a[i];
		chmx(l, 1ll);
		if(l<=r){
			X.upd(1,1,n, l, r, h[i] );
			Y.upd(1,1,n, l, r, -h[i] );
		}
		for(auto [l, id] : que[i]){
			// chmx(ans[id], ST.que(1,1,n, l,i));
			chmx(ans[id], X.que(1,1,n, l,i));
			chmx(ans[id], Y.que(1,1,n, l,i));
		}
		for(auto j : off[i]){ // idx yg jadi gk active
			// cout << j << " off\n";
			// upd ST (nyimpen kalo queL <= j) 
			X.que(1,1,n,j,j);
			Y.que(1,1,n,j,j);
			// ST.upd(1,1,n, j, X.que(1,1,n,j,j) );
			// ST.upd(1,1,n, j, Y.que(1,1,n,j,j) );
			// deactivate
			X.make(1,1,n, j, pii(-INF,-INF) );
			Y.make(1,1,n, j, pii(-INF,-INF) );
		}
	}
	for(int i=1; i<=Q; i++) 
		cout << ans[i] << " \n";
} 

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