Submission #204238

#	Time	Username	Problem	Language	Result	Execution time	Memory
204238		theStaticMind	Construction of Highway (JOI18_construction)	C++14	16 / 100	2049 ms	16280 KiB

construction

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;


struct Fenwick{
      vector<int> bit;
      int size;
      void modify(int j, int v){
            j++;
            for(; j < size; j += j & -j)bit[j] += v;
      }
      int query(int j){
            j++;
            int v = 0;
            for(; j > 0; j -= j & -j)v += bit[j];
            return v;
      }
      int rangequery(int a, int b){
            return query(b) - query(a - 1);
      }
      void rangeupdate(int a, int b, int v){
            modify(a, v);
            modify(b + 1, -v);
      }
      Fenwick(int s){
            s += 5;
            size = s;
            bit = vector<int>(s, 0);
      }
};

const int N = 1e5 + 5;

vector<int> adj[N];
vector<ii> Q;
vector<int> val(N);
vector<int> anc(N, 0);
vector<ii> W;


void dfs(int x, int pre){
	for(auto y : adj[x]){
		if(y == pre) continue;
		anc[y] = x;
		dfs(y, x);
	}
}

void query(int x){
	while(x != 0){
		W.pb({val[x], 1});
		x = anc[x];
	}
	reverse(all(W));
}
void update(int x, int v){
	while(x != 0){
		val[x] = v;
		x = anc[x];
	}
	reverse(all(W));
}

void compress(vector<ii>& arr){
	map<int,int> data;
	for(auto x : arr) data[x.first] = 0;
	int ind = sz(arr);
	for(auto& x : data)x.second = ind--;
	for(auto& x : arr) x.first = data[x.first];
}

int ans(vector<ii>& arr){
	compress(arr);
	Fenwick bit(sz(arr));
	int ret = 0;
	for(auto x : arr){
		ret += bit.query(x.first - 1);
		bit.modify(x.first, x.second);
	}
	return ret;
}

int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
     	int n;
      cin >> n;
      for(int i = 1; i <= n; i++) cin >> val[i];
      for(int i = 0; i < n - 1; i++){
      	int x, y;
      	cin >> x >> y;
      	adj[x].pb(y);
      	adj[y].pb(x);
      	Q.pb({x, y});
      }
      dfs(1, 0);

      for(auto p : Q){
      	query(p.first);
      	cout << ans(W) << "\n";
      	W.clear();
      	update(p.second, val[p.second]);
      }
}

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