제출 #491067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
491067		balbit	별자리 3 (JOI20_constellation3)	C++14	0 / 100	3 ms	5196 KiB

constellation3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = LLONG_MAX;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 2e5+5;


vector<pii> stars[maxn]; // stars in my region
int lc[maxn], rc[maxn], par[maxn];
int fa[21][maxn];
int L[maxn], R[maxn];
bool on[maxn];
namespace DSU{
    int par[maxn];
    int find(int x) {
        return x == par[x]? x : par[x] = find(par[x]);
    }
    void mrg(int a, int b) { // a is the new head
        a = find(a); b = find(b);
        MN(L[a], L[b]); MX(R[a], R[b]);
        par[b] = a;
    }
};

int a[maxn];
ll dp[maxn];

ll s[maxn];
void MO(int e, ll v) {
    for(++e; e<maxn; e+=e&-e) s[e] += v;
}
ll QU(int e) {
    ll re = 0;
    for(++e; e>0; e-=e&-e) {
        re += s[e];
    }
    return re;
}

signed main(){
    IOS();

    int n; cin>>n;
    vector<pii> who;
    REP(i,n) {
        cin>>a[i]; who.pb({a[i], i}); par[i] = L[i] = R[i] = i;
    }
    sort(ALL(who), [&](pii x, pii y){return x.f==y.f?x.s>y.s:x.f<y.f;});
    for(pii p : who) {
        int i = p.s;
        lc[i] = rc[i] = n+1;
        if(i && on[i-1]) {
            lc[i] = DSU::find(i-1); par[lc[i]] = i;
            DSU::mrg(i, i-1);
        }
        if(i!=n-1 && on[i+1]) {
            rc[i] = DSU::find(i+1); par[rc[i]] = i;
            DSU::mrg(i, i+1);
        }
        on[i] = 1;
    }
    for(int j = 0; j<20; ++j) {
        REP(i,n) {
            if(j == 0) fa[j][i] = par[i];
            else fa[j][i] = fa[j-1][fa[j-1][i]];
        }
    }
    int m; cin>>m;
    ll sig = 0;
    REP(i,m) {
        int x,y,v; cin>>x>>y>>v; --x; sig += v;
        int at = x;
        for(int j = 19; j>=0; --j) {
            if(a[fa[j][at]] < y) at = fa[j][at];
        }
        bug(i, at, fa[0][at]);
        stars[at].pb({x,y});
    }

    REP(ind,n) {
        int i = who[ind].s;
        dp[i] = dp[lc[i]] + dp[rc[i]];
        for(pii S : stars[i]) {
            if(S.f == i) {
                MX(dp[i], dp[lc[i]] + dp[rc[i]] + S.s);
            }else if (S.f < i) {
                MX(dp[i], QU(S.f) + dp[rc[i]] + S.s);
            }
        }
    }
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 65