Submission #317932

#	Time	Username	Problem	Language	Result	Execution time	Memory
317932		NintsiChkhaidze	Construction of Highway (JOI18_construction)	C++14	16 / 100	2074 ms	4856 KiB

construction

#include <bits/stdc++.h>
#define s second
#define f first
#define pb push_back
#define mod 1000000007
#define N 100005
#define ll long long
using namespace std;
int a[100005],fen[100005],p[100005];
pair<int,int> d[100005];
vector <int> v;
int get(int ind){
    int sum=0;
    while (ind > 0){
        sum+=fen[ind];
        ind-=(ind&(-ind));
    }
    return sum;
}
void upd(int ind,int val){
    while(ind < N){
        fen[ind]+=val;
        ind+=(ind&(-ind));
    }
}
int main(){
    int n;
    cin>>n;
    
    for (int i=1;i<=n;i++){
        int a;
        cin>>a;
        d[i].f = a,d[i].s = i;
    }
    sort(d+1,d+n+1);
    a[d[1].s] = 1;
    for (int i=2;i<=n;i++){
        if (d[i].f == d[i - 1].f) a[d[i].s] = a[d[i-1].s];
        else a[d[i].s] = a[d[i-1].s] + 1;
    }
    for (int i=1;i<n;i++){
        int x,y,X;
        cin>>x>>y;
        X = x;
        v.clear();
        while (p[x] >= 1)
            v.pb(x),x=p[x];
        
        v.pb(1);
        int ans=0;
        for (int j=v.size()-1;j>=0;j--){
            int x = get(n) - get(a[v[j]]);
            ans+=x;
            upd(a[v[j]],1);
        }
        for (int j=0;j<v.size();j++){
            upd(a[v[j]],-1);
            a[v[j]] = a[y];
        }
        p[y] = X;
        cout<<ans<<"\n";
    }
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int j=0;j<v.size();j++){
      |                      ~^~~~~~~~~

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