Submission #1305762

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

construction

#include <iostream>
#include <vector>
#include <set>
#include<algorithm>
#include<queue>
#include<map>
#include<math.h>
#include<assert.h>
#include<random>
#define ll long long
#define int ll
#define i32 __int32_t
#define i64 __int64_t
#define i128 __int128_t
#define db double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define bk back()
#define bg begin()
#define ed end()
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("avx,avx2,fma")
using namespace std;

const int LM=100100;
int N;
int C[LM];
int p[LM];
vector<int>z;
int pw[LM];

void init(){fill(pw+1,pw+N+1,0);}
void update(int x){for(int i=x; i<=N; i+=i&-i) pw[i]++;}
int Sum(int x){
    int ret=0;
    for(int i=x; i; i-=i&-i) ret+=pw[i];
    return ret;
}

signed main(){
    cin>>N;
    for(int i=1; i<=N; i++) cin>>C[i];
    for(int i=1; i<=N; i++) z.push_back(C[i]);
    sort(z.bg, z.ed);
    
    for(int i=1; i<=N; i++) C[i] = lower_bound(z.bg, z.ed, C[i])-z.bg+1;
    
    for(int i=1; i<N; i++){
        int u,v;cin>>u>>v;
        p[v]=u;
        vector<int>a;
        for(int i=u; i;i=p[i]) a.push_back(C[i]);
        reverse(a.bg, a.ed);
        init();
        
        int ans=0;
        for(int i=0; i<a.size(); i++){
            ans += i-Sum(a[i]);
            update(a[i]);
        }
        cout<<ans<<"\n";
        
        for(int i=u; i; i=p[i]) C[i]=C[v];
    }
}

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