Submission #1116941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116941		imarn	Construction of Highway (JOI18_construction)	C++14	100 / 100	617 ms	86232 KiB

construction

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define szz(r) (ll)r.size()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
const int mxn=1e5+5;
ll fw[mxn]{0};
vector<int>tmp;
void add(int i,int amt){
    i=upper_bound(all(tmp),i)-tmp.begin();
    for(;i<mxn;i+=i&-i)fw[i]+=amt;
}
ll qr(int i,ll rs=0){
    i=upper_bound(all(tmp),i)-tmp.begin();
    for(;i;i-=i&-i)rs+=fw[i];
    return rs;
}
vector<int>g[mxn];
int s[mxn]{0};
int a[mxn],b[mxn],sz[mxn],pr[mxn]{0},head[mxn]{0},id[mxn]{0},cur=0;
void dfs(int u,int p){
    sz[u]=1;pr[u]=p;
    for(auto v:g[u]){
        if(v==p)continue;
        dfs(v,u);sz[u]+=sz[v];
    }
}
void hld(int u,int p,int tp){
    head[u]=tp;id[u]=++cur;
    int hv=-1;
    for(auto v:g[u]){
        if(v==p)continue;
        if(hv==-1||sz[hv]<sz[v])hv=v;
    }if(hv==-1)return;
    hld(hv,u,tp);
    for(auto v:g[u]){
        if(v==p||v==hv)continue;
        hld(v,u,v);
    }
}
deque<pair<pii,int>>dq[mxn];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i],tmp.pb(s[i]);
    sort(all(tmp));tmp.erase(unique(all(tmp)),tmp.end());
    for(int i=1;i<=n-1;i++){
        cin>>a[i]>>b[i];g[a[i]].pb(b[i]);g[b[i]].pb(a[i]);
    }dfs(1,-1);hld(1,1,1);dq[1].push_front({{1,1},s[1]});
    for(int i=1;i<=n-1;i++){
        int x=a[i],y=b[i];
        vector<pair<pii,int>>rs;
        stack<pair<pii,int>>st;
        while(x!=-1){
            while(!dq[head[x]].empty()){
                auto it = dq[head[x]].front();
                if(it.f.s<=id[x])st.push(it),dq[head[x]].pop_front();
                else if(it.f.f<=id[x]){
                    dq[head[x]].pop_front();
                    dq[head[x]].push_front({{id[x]+1,it.f.s},it.s});
                    st.push({{it.f.f,id[x]},it.s});
                    break;
                }else break;
            }while(!st.empty())rs.pb(st.top()),st.pop();
            dq[head[x]].push_front({{id[head[x]],id[x]},s[y]});
            x=pr[head[x]];
        }if(dq[head[y]].empty())dq[head[y]].pb({{id[y],id[y]},s[y]});
        else dq[head[y]].back().f.s=id[y],dq[head[y]].back().s=s[y];
        ll ans=0;
        for(auto it : rs)ans+=qr(it.s-1)*(it.f.s-it.f.f+1),add(it.s,it.f.s-it.f.f+1);
        cout<<ans<<'\n';
        for(auto it : rs)add(it.s,-it.f.s+it.f.f-1);
    }
}

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