Submission #522060

#	Time	Username	Problem	Language	Result	Execution time	Memory
522060		Mahdi	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	843 ms	56140 KiB

constellation3

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int>pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
const int N=2e5+5;
int n, m, sz, a[N], cl[N], cr[N], x[N], y[N], c[N], mx[4*N], la[4*N], p[N], td[N];
ll dp[N], pd[N], mm[N], ans[4*N], fuck;
vector<pii>u[N];

int max(int x, int lx, int rx, int l, int r){
    if(lx>=r || rx<=l)
        return n;
    if(lx>=l && rx<=r)
        return mx[x];
    int mid=(lx+rx)/2;
    int l1=max(2*x+1, lx, mid, l, r);
    int r1=max(2*x+2, mid, rx, l, r);
    if(a[l1]<=a[r1])
        return r1;
    return l1;
}

void max(int x, int lx, int rx, int l, int r, ll v){
    if(rx<=l || lx>=r)
        return;
    if(lx>=l && rx<=r){
        ans[x]=max(ans[x], v);
        return;
    }
    int mid=(lx+rx)/2;
    if(la[x]){
        ans[2*x+1]=ans[2*x+2]=0;
        la[2*x+1]=la[2*x+2]=1;
        la[x]=0;
    }
    ans[2*x+1]=max(ans[x], ans[2*x+1]);
    ans[2*x+2]=max(ans[x], ans[2*x+2]);
    max(2*x+1, lx, mid, l, r, v);
    max(2*x+2, mid, rx, l, r, v);
}

ll num(int x, int l, int r, int y){
    if(r-l==1)
        return ans[x]+fuck;
    if(la[x]){
        la[2*x+1]=la[2*x+2]=1;
        ans[2*x+1]=ans[2*x+2]=0;
        la[x]=0;
    }
    ans[2*x+1]=max(ans[2*x+1], ans[x]);
    ans[2*x+2]=max(ans[2*x+2], ans[x]);
    int mid=(l+r)/2;
    if(y<mid)
        return num(2*x+1, l, mid, y);
    return num(2*x+2, mid, r, y);
}

void dsu(int l1, int r1, int l2, int r2){
    int w1=p[l1];
    int w2=p[l2];
    if(u[w1].size()>u[w2].size()){
        swap(w1, w2);
        swap(l1, l2);
        swap(r1, r2);
    }
    for(pii ww: u[w1]){
        dp[ww.S]+=pd[w1]-pd[w2];
        u[w2].push_back(ww);
        mm[w2]=max(mm[w2], dp[ww.S]+pd[w2]);
    }
    for(int i=l1;i<r1;++i)
        p[i]=w2;
}

ll sol(int l, int r){
    if(l==r)
        return 0;
    int id=max(0, 0, sz, l, r);
    int s1=td[l]-td[id], s2=td[id+1]-td[r];
    ll lr=0, zz=0, rl=0;
    if(s1<s2){
        ll z=sol(l, id);
        if(a[id]<n-1)
            lr=num(0, 0, sz, a[id]+1);
        else
            lr=z;
        la[0]=1;
        ans[0]=0;
        fuck=0;
        zz=sol(id+1, r);
        if(a[id]<n-1)
            rl=num(0, 0, sz, a[id]+1);
        else
            rl=zz;
        if(id>l){
            pd[p[l]]+=rl;
            mm[p[l]]+=rl;
            fuck+=lr;
            int v=p[l];
            for(pii w: u[v])
                max(0, 0, sz, w.F+1, n, dp[w.S]+pd[v]-fuck);
        }
        if(id+1<r){
            pd[p[id+1]]+=lr;
            mm[p[id+1]]+=lr;
        }
    }
    else{
        ll z=sol(id+1, r);
        if(a[id]<n-1)
            lr=num(0, 0, sz, a[id]+1);
        else
            lr=z;
        la[0]=1;
        ans[0]=0;
        fuck=0;
        zz=sol(l, id);
        if(a[id]<n-1)
            rl=num(0, 0, sz, a[id]+1);
        else
            rl=zz;
        if(id+1<r){
            pd[p[id+1]]+=rl;
            mm[p[id+1]]+=rl;
            fuck+=lr;
            int v=p[id+1];
            for(pii w: u[v])
                max(0, 0, sz, w.F+1, n, dp[w.S]+pd[v]-fuck);
        }
        if(id>l){
            pd[p[l]]+=lr;
            mm[p[l]]+=lr;
        }
    }
    for(pii w: u[id]){
        dp[w.S]=c[w.S]+lr+rl;
        mm[id]=max(mm[id], dp[w.S]);
        max(0, 0, sz, w.F+1, n, dp[w.S]-fuck);
    }
    if(id+1<r)
        dsu(id, id+1, id+1, r);
    if(id>l)
        dsu(l, id, id, r);
    return max(rl+lr, mm[p[l]]);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>a[i];
        --a[i];
    }
    a[n]=-1;
    cin>>m;
    for(int i=0;i<m;++i){
        cin>>x[i]>>y[i]>>c[i];
        u[--x[i]].push_back({--y[i], i});
    }
    for(int i=n-1;i>=0;--i){
        sort(all(u[i]));
        td[i]=td[i+1]+u[i].size();
    }
    sz=1;
    while(sz<n)
        sz*=2;
    iota(mx+sz-1, mx+n+sz-1, 0);
    for(int i=sz-2;i>=0;--i){
        if(a[mx[2*i+1]]<a[mx[2*i+2]])
            mx[i]=mx[2*i+2];
        else
            mx[i]=mx[2*i+1];
    }
    iota(p, p+n, 0);
    ll z=0;
    for(int i=0;i<m;++i)
        z+=c[i];
    z-=sol(0, n);
    cout<<z<<'\n';
}

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