Submission #820584

#	Time	Username	Problem	Language	Result	Execution time	Memory
820584		irmuun	Construction of Highway (JOI18_construction)	C++17	0 / 100	0 ms	320 KiB

construction

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct segtree{
    ll n;
    vector<ll>d;
    vector<ll>u;
    segtree(ll x){
        n=x;
        u.resize(n,0);
        d.resize(4*n);
        build(1,1,n);
    }
    void build(ll node,ll l,ll r){
        if(l==r){
            d[node]=u[l-1];
            return;
        }
        ll mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        d[node]=d[node*2]+d[node*2+1];
    }
    ll query(ll node,ll l,ll r,ll L,ll R){
        if(l > R || r < L || L > R){
            return 0;
        }
        if(L <= l && r <= R){
            return d[node];
        }
        ll mid=(l+r)/2;
        return query(node*2,l,mid,L,R)+query(node*2+1,mid+1,r,L,R);
    }
    void update(ll node,ll l,ll r,ll k,ll val){
        if(l>k || r<k)return;
        if(l==r){
            d[node]=val;
            return;
        }
        ll mid=(l+r)/2;
        update(node*2,l,mid,k,val);
        update(node*2+1,mid+1,r,k,val);
        d[node]=d[node*2]+d[node*2+1];
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n;
    cin>>n;
    ll c[n+1];
    for(ll i=1;i<=n;i++){
        cin>>c[i];
    }
    ll p[n+1];
    p[1]=0;
    for(ll i=1;i<n;i++){
        ll a,b;
        cin>>a>>b;
        p[b]=a;
        vector<pair<ll,ll>>v;
        vector<ll>u;
        ll cur=b,j=0;
        while(cur>0){
            j++;
            v.pb({c[cur],-j});
            u.pb(cur);
            cur=p[cur];
        }
        segtree sg(v.size());
        sort(all(v));
        ll ans=0;
        for(auto [x,j]:v){
            j=-j;
            ans+=sg.query(1,1,v.size(),1,j-1);
            sg.update(1,1,v.size(),j,1);
        }
        cout<<ans<<"\n";
        for(auto x:u){
            c[x]=c[b];
        }
    }
}

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