제출 #1180287

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180287		ByeWorld	Two Antennas (JOI19_antennas)	C++20	100 / 100	571 ms	73320 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); }
void maximize(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 SegmentTreeLazy{
    struct Node{
        ll a, b, lazy;
        Node(){
            a = b = lazy = -INF;
        }
    };

    int n;
    vector<Node> a;

    SegmentTreeLazy(int n): n(n){
        a.resize(n * 4 + 4);
    }

    void apply_a(int id, pair<ll, ll> val){
        a[id].a = val.first;
        a[id].b = val.first + val.second;
    }

    void apply_b(int id, ll val){
        maximize(a[id].b, a[id].a + val);
        maximize(a[id].lazy, val);
    }

    void down(int id){
        apply_b(id * 2, a[id].lazy);
        apply_b(id * 2 + 1, a[id].lazy);
        a[id].lazy = -INF;
    }

    Node combine(Node a, Node b){
        Node c;
        c.a = max(a.a, b.a);
        c.b = max(a.b, b.b);
        return c;
    }

    void update_a(int i, pair<ll, ll> val, int l, int r, int id){
        if (l == r){
            apply_a(id, val);
            return;
        }
        if (a[id].lazy != -INF) down(id);
        int mid = (l + r) >> 1;
        if (i <= mid) update_a(i, val, l, mid, id * 2);
        else update_a(i, val, mid + 1, r, id * 2 + 1);
        a[id] = combine(a[id * 2], a[id * 2 + 1]);
    }
    void update_a(int i, pair<ll, ll> val){
        update_a(i, val, 1, n, 1);
    }

    void update_b(int u, int v, ll val, int l, int r, int id){
        if (u <= l && r <= v){
            apply_b(id, val);
            return;
        }
        if (a[id].lazy != -INF) down(id);
        int mid = (l + r) >> 1;
        if (u <= mid) update_b(u, v, val, l, mid, id * 2);
        if (v > mid) update_b(u, v, val, mid + 1, r, id * 2 + 1);
        a[id] = combine(a[id * 2], a[id * 2 + 1]);
    }
    void update_b(int l, int r, ll val){
        update_b(l, r, val, 1, n, 1);
    }

    ll get(int u, int v, int l, int r, int id){
        if (u <= l && r <= v) return a[id].b;
        if (a[id].lazy != -INF) down(id);
        int mid = (l + r) >> 1;
        ll ans = -INF;
        if (u <= mid) maximize(ans, get(u, v, l, mid, id * 2));
        if (v > mid) maximize(ans, get(u, v, mid + 1, r, id * 2 + 1));
        return ans;
    }
    ll get(int u, int v){return get(u, v, 1, n, 1);}
};  
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);
    SegmentTreeLazy X(n), Y(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.update_a(j, pii(-h[j],-INF) );
			Y.update_a(j, pii(h[j],-INF) );
		}
		int l = i-b[i], r = i-a[i];
		chmx(l, 1ll);
		if(l<=r){
			X.update_b(l, r, h[i] );
			Y.update_b(l, r, -h[i] );
		}
		for(auto [l, id] : que[i]){
			chmx(ans[id], ST.que(1,1,n,l,i));
			chmx(ans[id], X.get(l,i));
			chmx(ans[id], Y.get(l,i));
		}
		for(auto j : off[i]){ // idx yg jadi gk active
			// cout << j << " off\n";
			// upd ST (nyimpen kalo queL <= j)
			ST.upd(1,1,n, j, X.get(j,j) );
			ST.upd(1,1,n, j, Y.get(j,j) );
			// deactivate
			X.update_a(j, pii(-INF,-INF) );
			Y.update_a(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