Submission #212409

#	Time	Username	Problem	Language	Result	Execution time	Memory
212409		medk	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	531 ms	49116 KiB

constellation3

#include <bits/stdc++.h>

#define ld long double
#define ll long long
#define pb push_back
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())

using namespace std;

ll n,m;
vector<ll> bX;
vector<vector<ll>>bY;
vector<vector<pair<ll,ll>>> sX,sY;
vector<pair<ll,pair<ll,ll>>> dsu;
vector<ll> sgt,lazy;

ll getp(ll x)
{
    if(x==dsu[x].x) return x;
    return dsu[x].x=getp(dsu[x].x);
}
void connect(ll u, ll v)
{
    u=getp(u), v=getp(v);
    if(dsu[u].y.y-dsu[u].y.x<dsu[v].y.y-dsu[v].y.x) swap(u,v);
    dsu[v].x=u;
    dsu[u].y.x=min(dsu[u].y.x,dsu[v].y.x);
    dsu[u].y.y=max(dsu[u].y.y,dsu[v].y.y);
}

void upd(ll a, ll b, ll val, ll p=1, ll l=0, ll r=n-1)
{
    if(lazy[p])
    {
        sgt[p]+=lazy[p];
        if(l!=r)
        {
            lazy[p*2]+=lazy[p];
            lazy[p*2+1]+=lazy[p];
        }
        lazy[p]=0;
    }
    if(l>=a && r<=b)
    {
        sgt[p]+=val;
        if(l!=r)
        {
            lazy[p*2]+=val;
            lazy[p*2+1]+=val;
        }
        return;
    }
    ll md=(l+r)/2;
    if(l<=b && md>=a) upd(a,b,val,p*2,l,md);
    if(md+1<=b && r>=a) upd(a,b,val,p*2+1,md+1,r);
    sgt[p]=max(sgt[p*2],sgt[p*2+1]);
}

ll getmx(ll a, ll b, ll p=1, ll l=0, ll r=n-1)
{
    if(lazy[p])
    {
        sgt[p]+=lazy[p];
        if(l!=r)
        {
            lazy[p*2]+=lazy[p];
            lazy[p*2+1]+=lazy[p];
        }
        lazy[p]=0;
    }
    if(l>=a && r<=b) return sgt[p];
    ll md=(l+r)/2;
    ll ret=0;
    if(l<=b && md>=a) ret=getmx(a,b,p*2,l,md);
    if(md+1<=b && r>=a) ret=max(ret,getmx(a,b,p*2+1,md+1,r));
    return ret;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    bY.resize(n+1), sX.resize(n), sY.resize(n+1), sgt.resize(4*n), lazy.resize(4*n);
    for(ll i=0;i<n;i++) dsu.pb({i,{i,i}});
    for(ll i=0;i<n;i++)
    {
        ll Ai; cin>>Ai;
        Ai--;
        bX.pb(Ai);
        bY[Ai].pb(i);
    }
    ll ans=0;
    cin>>m;
    for(ll i=0;i<m;i++)
    {
        ll x,y; ll c; cin>>x>>y>>c;
        x--,y--;
        sX[x].pb({y,c});
        ans+=c;
    }
    for(ll i=0;i<n;i++)
    {
        sort(all(sX[i]));
        ll prev=0;
        for(auto p:sX[i])
        {
            if(p.y<=prev) continue;
            sY[p.x].pb({i,p.y-prev});
            prev=p.y;
        }
    }
    vector<bool> started(n,0);
    for(ll i=0;i<=n;i++)
    {
        for(auto p:sY[i])
            upd(p.x,p.x,p.y);
        for(ll bld:bY[i])
        {
            ll lV=0, rV=0;
            if(bld>0) if(started[bld-1])
            {
                ll par=getp(bld-1);
                ll L=dsu[par].y.x, R=dsu[par].y.y;
                lV=getmx(L,R);
            }
            if(bld<n-1) if(started[bld+1])
            {
                ll par=getp(bld+1);
                ll L=dsu[par].y.x, R=dsu[par].y.y;
                rV=getmx(L,R);
                upd(L,R,lV);
            }
            if(bld>0) if(started[bld-1])
            {
                ll par=getp(bld-1);
                ll L=dsu[par].y.x, R=dsu[par].y.y;
                upd(L,R,rV);
            }
            if(bld>0) if(started[bld-1]) connect(bld,bld-1);
            if(bld<n-1) if(started[bld+1]) connect(bld,bld+1);
            started[bld]=1;
            upd(bld,bld,lV+rV);
        }
    }
    cout<<ans-sgt[1]<<'\n';
    return 0;
}

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