Submission #956700

#	Time	Username	Problem	Language	Result	Execution time	Memory
956700		andrei_boaca	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	585 ms	96632 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll n,A[300005],m,total;
ll up[300005],down[300005];
vector<ll> who[300005];
vector<ll> add[300005];
ll in[300005],out[300005],timp,dp[300005];
struct star
{
    ll x,y,c;
} v[300005];
struct event
{
    ll tip,poz; /// 0 -> zid, 1 -> stea
};
vector<event> ev[300005];
set<pair<pll,ll>> setik;
ll par[300005];
vector<ll> muchii[300005];
bool comp(event a, event b)
{
    return a.tip<b.tip;
}
int nrnodes;
void build(int nod)
{
    timp++;
    in[nod]=timp;
    for(int i:muchii[nod])
        if(i!=par[nod])
        {
            par[i]=nod;
            build(i);
        }
    out[nod]=timp;
}
ll aib[300005];
ll lsb(ll x)
{
    return x&(-x);
}
void update(ll poz,ll val)
{
    for(int i=poz;i<=nrnodes;i+=lsb(i))
        aib[i]+=val;
}
ll suma(ll poz)
{
    ll rez=0;
    for(int i=poz;i>=1;i-=lsb(i))
        rez+=aib[i];
    return rez;
}
void intervupd(ll l,ll r,ll val)
{
    update(l,val);
    update(r+1,-val);
}
void dfs(int nod)
{
    ll sum=0;
    for(ll i:muchii[nod])
    {
        dfs(i);
        sum+=dp[i];
    }
    intervupd(in[nod],in[nod],sum);
    for(ll i:muchii[nod])
    {
        sum-=dp[i];
        intervupd(in[i],out[i],sum);
        sum+=dp[i];
    }
    dp[nod]=sum;
    for(ll ind:add[nod])
    {
        ll val=suma(in[down[ind]])+v[ind].c;
        dp[nod]=max(dp[nod],val);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>A[i];
        ev[A[i]].push_back({0,i});
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>v[i].x>>v[i].y>>v[i].c;
        total+=v[i].c;
        ev[v[i].y].push_back({1,i});
        who[v[i].x].push_back(i);
    }
    setik.insert({{1,n},1});
    nrnodes=1;
    for(int lin=n;lin>=1;lin--)
    {
        sort(ev[lin].begin(),ev[lin].end(),comp);
        for(event p:ev[lin])
        {
            int tip=p.tip;
            if(tip==0)
            {
                int poz=p.poz;
                auto it=prev(setik.lower_bound({{poz+1,0},0}));
                int l=(*it).first.first;
                int r=(*it).first.second;
                int nod=(*it).second;
                for(int i:who[poz])
                    down[i]=nod;
                setik.erase(it);
                int l1=l,r1=poz-1;
                int l2=poz+1,r2=r;
                if(l1<=r1)
                {
                    nrnodes++;
                    setik.insert({{l1,r1},nrnodes});
                    muchii[nod].push_back(nrnodes);
                    par[nrnodes]=nod;
                }
                if(l2<=r2)
                {
                    nrnodes++;
                    setik.insert({{l2,r2},nrnodes});
                    muchii[nod].push_back(nrnodes);
                    par[nrnodes]=nod;
                }
            }
            else
            {
                int ind=p.poz;
                auto it=prev(setik.lower_bound({{v[ind].x+1,0},0}));
                int nod=(*it).second;
                up[ind]=nod;
                add[nod].push_back(ind);
            }
        }
    }
    build(1);
    dfs(1);
    cout<<total-dp[1];
    return 0;
}

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