Submission #246360

#	Time	Username	Problem	Language	Result	Execution time	Memory
246360		fivefourthreeone	Construction of Highway (JOI18_construction)	C++17	100 / 100	1097 ms	31096 KiB

construction

#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a); i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"debug"<<endl
 
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
const int NINF = 0x3f3f3f40;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0x3f3f3f3f3f3f3f40;
const int mxN = 100001;
int n;
int cnt = 0;
ttgl inout[mxN];
ttgl edges[mxN];
set<int> stt;
map<int, int> mp;
int arr[mxN];
int seg[4*mxN];
int par[mxN][18];
vector<int> adj[mxN];
void upd(int p, int val) {
    for(seg[p+=2*n] = val; p>1; p>>=1) seg[p>>1] = max(seg[p], seg[p^1]);
}
int qmax(int l, int r) {
    int res = 0;
    r++;
    for(l+=2*n, r+=2*n; l<r; l>>=1, r>>=1) {
        if(l&1) res= max(res, seg[l++]);
        if(r&1) res = max(res, seg[--r]);
    }
    return res;
}
int BIT[mxN];
void add(int i, int val) {
    while(i<=n) {
        BIT[i]+= val;
        i +=i&-i;
    }
}
void del(int i) {
    while(i<=n) {
        BIT[i] = 0;
        i +=i&-i;
    }
}
int sum (int i) {
    int res = 0;
    while(i>0) {
        res+=BIT[i];
        i-=i&-i;
    }
    return res;
}
void dfs(int u, int p) {
    par[u][0] = p;
    inout[u].first = cnt++;
    for(int v: adj[u]) {
        if(v==p)continue;
        dfs(v, u);
    }
    inout[u].second = cnt++;
}
int query(int k) {
    //cout<<"\n";
    //cout<<k<<" "<<inout[k].first<<" "<<inout[k].second<<" "<<qmax(inout[k].first, inout[k].second)<<" hi\n";
    return qmax(inout[k].first, inout[k].second);
}
int main()
{
    //freopen("filename.in", "r", stdin);
    //freopen("filename.out", "w", stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    owo(i, 0, n) {
        cin>>arr[i];
        stt.insert(arr[i]);
    }
    int idx = 0;
    auto it = stt.begin();
    while(it!=stt.end()) {
        mp[*it] = idx++;
        it++;
    }
    owo(i, 0, n) {
        arr[i] = mp[arr[i]];
    }
    owo(i, 0, n-1) {
        cin>>edges[i].first>>edges[i].second;
        edges[i].first--;
        edges[i].second--;
        adj[edges[i].first].senpai(edges[i].second);
        adj[edges[i].second].senpai(edges[i].first);
    }
    dfs(0, -1);
    owo(lg, 1, 18) {
        owo(i, 0, n) {
            if(par[i][lg-1]==-1) {
                par[i][lg] = -1;
            }else {
                par[i][lg] = par[par[i][lg-1]][lg-1];
            }
        }
    }
    owo(i, 0, 2*mxN) {
        seg[i] = -1;
    }
    upd(inout[0].first, 0);
    owo(i, 1, n) {
        int a = edges[i-1].first;
        int b = edges[i-1].second;
        int ans = 0;
        vector<int> path;
        //cout<<i<<"\n";
        int val = query(a)==0 ? arr[a] : arr[edges[query(a)-1].second];
        while(a!=-1) {
            int num= 1;
            //cout<<a<<" ";
            uwu(i, 18, 0) {
                if(par[a][i]!=-1&&query(par[a][i])==query(a)) {
                    a = par[a][i];
                    num+=(1<<i);
                }
            }
            //cout<<a<<" "<<num<<" "<<val<<" "<<sum(val+1)<<"\n";
            ans+=num*sum(val);
            add(val+1, num);
            path.senpai(val+1);
            a = par[a][0];
            val = arr[edges[query(a)-1].second];
            //cout<<query(a)<<"\n";
        }
        for(int k: path) {
            del(k);
        }
        cout<<ans<<"\n";
        upd(inout[b].first, i);
        //cout<<inout[b].first<<" "<<i<<" cool\n";
    }
    return 0;
}

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