Submission #113999

#	Time	Username	Problem	Language	Result	Execution time	Memory
113999		shayan_p	Construction of Highway (JOI18_construction)	C++14	16 / 100	2019 ms	2296 KiB

construction

// High above the clouds there is a rainbow...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=1e5+10,mod=1e9+7;
const ll inf=1e18;

int a[maxn],fn[maxn],par[maxn];

void add(int pos,int x){
    for(pos=pos+3;pos<maxn;pos+=(pos & -pos))
	fn[pos]+=x;
}
int ask(int pos){
    int ans=0;
    for(pos=pos+3;pos>0;pos-=(pos & -pos))
	ans+=fn[pos];
    return ans;
}

int arr[maxn],C;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n;cin>>n;
    for(int i=0;i<n;i++){
	cin>>a[i];
	arr[i]=a[i];
    }
    sort(arr,arr+n);
    C=unique(arr,arr+n)-arr;
    for(int i=0;i<n;i++){
	a[i]=lower_bound(arr,arr+C,a[i])-arr;
    }
	
    par[0]=-1;
    for(int i=0;i<n-1;i++){
	int A,B;cin>>A>>B;
	par[--B]=--A;
	ll ans=0;
	int x=A;
	while(x>=0){
	    ans+=ask(a[x]-1);
	    add(a[x],1);
	    x=par[x];
	}
	x=A;
	while(x>=0){
	    add(a[x],-1);
	    a[x]=a[B];
	    x=par[x];
	}
	cout<<ans<<"\n";
    }
    return 0;
}
// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn.
//  * Overflows.

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