Submission #626712

#	Time	Username	Problem	Language	Result	Execution time	Memory
626712		MatBad	Construction of Highway (JOI18_construction)	C++14	16 / 100	349 ms	544 KiB

construction

#include<bits/stdc++.h>
//#pragma GCC optimize ("O2,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
using namespace std;
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define pc __builtin_popcount
#define cl __builtin_clz
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define debug(x) cerr<<#x<<" : &"<<x<<"&\n"
#define wall() cerr<<'\n'<<"-------------------------------\n"
typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;
typedef pair<bool , pii> piii;

const ll 
	MX=5e3+5,
	M=600,
	MOD = 1e9+7, 
	inf = 1e9+20, 
	infl = 1e16,
	LOG = 18,
	A = 27,
	del = 10067;

int n, fen[MX], p[MX], c[MX];

void add(int x, int N){
	while(x<=N){
		fen[x]++;
		x+= x&(-x);
	}
}

int ask(int x, int N){
	int res=0;
	while(x){
		res+= fen[x];
		x-= x&(-x);
	}
	return res;
}

int cntinv(vector<int>& vec){
	int N = vec.size();
	pii g[N+1]={};
	int rnk[N+1]={};
	FOR(i, 1, N) g[i] = pii(vec[i-1], i-1);
	sort(g+1, g+N+1);
	FOR(i, 1, N) rnk[g[i].S] = rnk[g[i-1].S]+(g[i].F>g[i-1].F);
	memset(fen, 0, (N+1)*sizeof(int));
	int res=0;
	FOR(i, 0, N-1){
		res+= i-ask(rnk[i], N);
		add(rnk[i], N);
	}
	return res;
}

void solve(int v){
	vector<int> vec;
	for(int u=p[v]; u!=0; u=p[u]) vec.pb(c[u]);
	reverse(vec.begin(), vec.end());
	cout<<cntinv(vec)<<'\n';;
	for(int u=p[v]; u!=0; u=p[u]) c[u]=c[v]; 
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	p[1] = 0;
	FOR(i, 1, n) cin>>c[i];
	FOR(i, 1, n-1){
		int u, v;
		cin>>u>>v;
		p[v] = u;
		solve(v);
	}
}

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