Submission #1223701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223701		vivkostov	Construction of Highway (JOI18_construction)	C++20	16 / 100	2095 ms	30096 KiB

construction

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
const long long int inf=1e9+7;
long long int n,a[100005],aa[100005],b[100005],c[100005],dp[100005],ind[100005],orig[100005],br,lazy[400005],lead[100005],up[100005],p[400005],mi[400005],ma[400005],le;
vector<long long int>v[100005];
map<long long int,long long int>m;
void make_dp(long long int beg,long long int par)
{
    long long int w;
    dp[beg]=1;
    up[beg]=par;
    for(long long int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(w!=par)
        {
            make_dp(w,beg);
            dp[beg]+=dp[w];
        }
    }
}
void make_ind(long long int beg,long long int par,long long int l)
{
    br++;
    ind[beg]=br;
    orig[br]=beg;
    lead[beg]=l;
    long long int w,ma=0,to=0;
    for(long long int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(w!=par)
        {
            if(ma<dp[w])
            {
                ma=dp[w];
                to=w;
            }
        }
    }
    if(to)make_ind(to,beg,l);
    for(long long int i=0;i<v[beg].size();i++)
    {
        w=v[beg][i];
        if(w!=par&&w!=to)
        {
            make_ind(w,beg,w);
        }
    }
}
void prec()
{
    for(long long int i=1;i<=n*4;i++)
    {
        mi[i]=inf;
    }
    for(long long int i=1;i<=n;i++)
    {
        aa[i]=a[i];
    }
    sort(aa+1,aa+n+1);
    long long int num=1;
    for(long long int i=1;i<=n;i++)
    {
        if(aa[i]!=aa[i+1])
        {
            m[aa[i]]=num;
            num++;
        }
    }
    for(long long int i=1;i<=n;i++)
    {
        a[i]=m[a[i]];
    }
}
void h_update(long long int l,long long int r,long long int q,long long int h,long long int st)
{
    if(l>q||r<q)return;
    if(l==r)
    {
        p[h]+=st;
        return;
    }
    long long int mid=(l+r)/2;
    h_update(l,mid,q,h*2,st);
    h_update(mid+1,r,q,h*2+1,st);
    p[h]=p[h*2]+p[h*2+1];
}
long long int h_query(long long int l,long long int r,long long int ql,long long int qr,long long int h)
{
    if(l>qr||r<ql)return 0;
    if(l>=ql&&r<=qr)return p[h];
    long long int mid=(l+r)/2;
    return h_query(l,mid,ql,qr,h*2)+h_query(mid+1,r,ql,qr,h*2+1);
}
void h_clear(long long int l,long long int r,long long int h)
{
    if(l==r)
    {
        p[h]=0;
        return;
    }
    long long int mid=(l+r)/2;
    if(p[h*2])h_clear(l,mid,h*2);
    if(p[h*2+1])h_clear(mid+1,r,h*2+1);
    p[h]=0;
}
void push_lazy(long long int h)
{
    if(lazy[h])
    {
        mi[h]=lazy[h];
        ma[h]=lazy[h];
        lazy[h*2]=lazy[h];
        lazy[h*2+1]=lazy[h];
        lazy[h]=0;
    }
}
void check(long long int l,long long int r,long long int h)
{
    push_lazy(h);
    cout<<l<<" "<<r<<" "<<mi[h]<<" "<<ma[h]<<" "<<h<<endl;
    if(l==r)return;
    long long int mid=(l+r)/2;
    check(l,mid,h*2);
    check(mid+1,r,h*2+1);
    mi[h]=min(mi[h*2],mi[h*2+1]);
    ma[h]=max(ma[h*2],ma[h*2+1]);
}
void update(long long int l,long long int r,long long int ql,long long int qr,long long int h,long long int st)
{
    push_lazy(h);
    if(l>qr||r<ql)return;
    if(l>=ql&&r<=qr)
    {
        lazy[h]=st;
        push_lazy(h);
        //cout<<l<<" "<<r<<" "<<lazy[h]<<" "<<mi[h]<<" "<<h<<" ! "<<endl;
        //if(mi[h]==4)check(1,n,1);
        return;
    }
    long long int mid=(l+r)/2;
    update(l,mid,ql,qr,h*2,st);
    update(mid+1,r,ql,qr,h*2+1,st);
    mi[h]=min(mi[h*2],mi[h*2+1]);
    ma[h]=max(ma[h*2],ma[h*2+1]);
}
long long int get_value(long long int l,long long int r,long long int q,long long int h)
{
    push_lazy(h);
    if(l>q||r<q)return 0;
    if(l==r)return mi[h];
    long long int mid=(l+r)/2;
    return max(get_value(l,mid,q,h*2),get_value(mid+1,r,q,h*2+1));
}
void query(long long int l,long long int r,long long int ql,long long int qr,long long int h,long long int val)
{
    //cout<<l<<" "<<r<<" "<<mi[h]<<" "<<ma[h]<<" "<<ql<<" "<<qr<<endl;
    push_lazy(h);
    if(l==r)
    {
        if(mi[h]==val)
        {
            //cout<<val<<" "<<mi[l]<<endl;
            le=l;
        }
        return;
    }
    push_lazy(h*2);
    push_lazy(h*2+1);
    long long int mid=(l+r)/2;
    //cout<<mi[h*2+1]<<" "<<val<<" "<<mid+1<<endl;
    if(mid<ql||((mi[h*2+1]!=val||ma[h*2+1]!=val)&&mid+1<=qr))
    {
        //cout<<"!!!!"<<endl;
        query(mid+1,r,ql,qr,h*2+1,val);
    }
    else
    {
        le=mid+1;
        query(l,mid,ql,qr,h*2,val);
    }
}
void get_otg(long long int start)
{
    long long int cur=start,otg=0,top,br=0,old,val;
    //cout<<start<<endl;
    while(true)
    {
        top=lead[cur];
        old=cur;
        val=get_value(1,n,ind[cur],1);
        le=ind[cur];
        query(1,n,ind[top],ind[cur],1,val);
        //cout<<le<<endl;
        cur=orig[le];
        //cout<<endl;
        //check(1,n,1);
        //cout<<endl;
        br+=ind[old]-ind[cur]+1;
        //cout<<cur<<" "<<br<<" "<<val<<" "<<top<<endl;
        if(cur==1||val!=get_value(1,n,ind[up[cur]],1))
        {
            otg+=br*h_query(1,n,1,val-1,1);
            h_update(1,n,val,1,br);
            br=0;
            if(cur==1)break;
        }
        cur=up[cur];
    }
    //cout<<endl<<endl;
    cout<<otg<<endl;
}
void fix_tree(long long int cur,long long int st)
{
    h_clear(1,n,1);
    long long int top;
    while(cur!=0)
    {
        top=lead[cur];
        update(1,n,ind[top],ind[cur],1,st);
        //check(1,n,1);
        //cout<<endl<<endl;
        cur=up[top];
        if(cur==0)return;
    }
}
void read()
{
    cin>>n;
    for(long long int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(long long int i=1;i<n;i++)
    {
        cin>>b[i]>>c[i];
        v[b[i]].push_back(c[i]);
        v[c[i]].push_back(b[i]);
    }
    prec();
    make_dp(1,0);
    make_ind(1,0,1);
    update(1,n,1,1,1,a[1]);
    //check(1,n,1);
    for(long long int i=1;i<n;i++)
    {
        get_otg(b[i]);
        fix_tree(c[i],a[c[i]]);
        //cout<<endl<<endl;
        //check(1,n,1);
    }
}
int main()
{
    speed();
    read();
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 0 / 84