oj.uz

Submission #212408

# Submission time Handle Problem Language Result Execution time Memory
212408 2020-03-22T21:50:01 Z medk Constellation 3 (JOI20_constellation3) C++14
14 / 100
 9 ms 768 KB 
#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) 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) if(started[bld+1]) connect(bld,bld+1);
            started[bld]=1;
            upd(bld,bld,lV+rV);
        }
    }
    cout<<fixed<<ans-sgt[1]<<'\n';
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 512 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 512 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 7 ms 768 KB Output is correct
24 Correct 8 ms 768 KB Output is correct
25 Correct 7 ms 768 KB Output is correct
26 Correct 7 ms 768 KB Output is correct
27 Correct 8 ms 768 KB Output is correct
28 Correct 9 ms 768 KB Output is correct
29 Correct 7 ms 768 KB Output is correct
30 Correct 8 ms 768 KB Output is correct
31 Correct 8 ms 768 KB Output is correct
32 Correct 7 ms 768 KB Output is correct
33 Correct 7 ms 768 KB Output is correct
34 Correct 8 ms 768 KB Output is correct
35 Incorrect 7 ms 768 KB Output isn't correct
36 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 512 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 7 ms 768 KB Output is correct
24 Correct 8 ms 768 KB Output is correct
25 Correct 7 ms 768 KB Output is correct
26 Correct 7 ms 768 KB Output is correct
27 Correct 8 ms 768 KB Output is correct
28 Correct 9 ms 768 KB Output is correct
29 Correct 7 ms 768 KB Output is correct
30 Correct 8 ms 768 KB Output is correct
31 Correct 8 ms 768 KB Output is correct
32 Correct 7 ms 768 KB Output is correct
33 Correct 7 ms 768 KB Output is correct
34 Correct 8 ms 768 KB Output is correct
35 Incorrect 7 ms 768 KB Output isn't correct
36 Halted 0 ms 0 KB -