Submission #204295

#	Time	Username	Problem	Language	Result	Execution time	Memory
204295		theStaticMind	Construction of Highway (JOI18_construction)	C++14	100 / 100	635 ms	27112 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<long long int> bit;
      int size;
      void modify(int j, long long int v){
            j++;
            for(; j < size; j += j & -j)bit[j] += v;
      }
      long long int query(int j){
            j++;
            long long int v = 0;
            for(; j > 0; j -= j & -j)v += bit[j];
            return v;
      }
      long long int rangequery(long long int a, long long int b){
            return query(b) - query(a - 1);
      }
      void rangeupdate(long long int a, long long int b, long long int v){
            modify(a, v);
            modify(b + 1, -v);
      }
      Fenwick(int s){
            s += 5;
            size = s;
            bit = vector<long long int>(s, 0);
      }
} bit(1e5 + 10);

const int N = 1e5 + 5;

vector<int> adj[N];
vector<int> sub(N, 1);
vector<ii> Q(N);
vector<int> val(N);
vector<int> segind(N, 0);
vector<int> segid(N, 0);
vector<ii> seg[N];
vector<int> who[N];
vector<int> anc(N, 0);
vector<ii> ptr(N, {N, 0});
vector<int> S(N, 0);
vector<ii> W(N);
int C = 0;
int ind = 0;

void push(vector<ii>& seg, int j){
	if(j * 2 < sz(seg) && seg[j].first != N){
		seg[j * 2] = seg[j];
		seg[j * 2 + 1] = seg[j];
		seg[j] = {N, 0};
	}
}


void update(int x){
	int id = segid[x];
	int ind = segind[x];
	ii& p = seg[id][sz(seg[id]) - S[id] + ind];
	if(p.first != N) ptr[x] = p;
	p = {N, 0};
}
void updown(vector<ii>& seg, int j, int a, int x, int y){
	if(x == a && y == a) return;
	push(seg, j);
	int mid = (x + y) / 2;
	if(a <= mid) updown(seg, j * 2, a, x, mid);
	else updown(seg, j * 2 + 1, a, mid + 1, y);
}

void update(vector<ii>& seg, int j, int a, int b, int x, int y, ii v){
	if(y < a || b < x) return;
	push(seg, j);
	if(a <= x && y <= b){
		seg[j] = v;
	}
	else{
		update(seg, j * 2, a, b, x, (x + y) / 2, v);
		update(seg, j * 2 + 1, a, b, (x + y) / 2 + 1, y, v);
	}
}
void update(int x, int v){
	int id = segid[x];
	int ind = segind[x];
	update(seg[id], 1, 0, ind, 0, S[id] - 1, {v, ind});

	if(id == 0) return;
	update(anc[who[id][0]], v);
}
void query(int x){
	int id = segid[x];
	int ind = segind[x];
	if(id != 0) query(anc[who[id][0]]);
	int currind = 0, curr = who[id][0];
	while(currind <= ind){
		updown(seg[id], 1, currind, 0, S[id] - 1);
		update(curr);
		int nextind = min(ind, ptr[curr].second);
		W[C++] = {ptr[curr].first, nextind - currind + 1};
		currind = nextind + 1;
		curr = who[id][currind];
	}
}

void build(vector<ii>& seg, int id){
	seg = vector<ii> (S[id], {N, 0});
	S[id] = (1 << (int)ceil(log2(seg.size())));
	int l = S[id] - sz(seg);

	for(int i = 0; i < l; i++)seg.pb({N, 0});
	reverse(all(seg));
	for(int i = 1; i < sz(seg); i += 2) seg.pb({N, 0});
	seg.pb({'o','O'});
	reverse(all(seg));
}


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

void dfs_hld(int x, int pre){
	int sp = -1;
	int mx = -1;
	for(auto y : adj[x]){
		if(y == pre)continue;
		if(mx < sub[y]){
			mx = sub[y];
			sp = y;
		}
	}
	if(sp == -1)return;

	segind[sp] = segind[x] + 1;
	segid[sp] = ind;
	S[ind]++;
	who[ind].pb(sp);
	dfs_hld(sp, x);
	for(auto y : adj[x]){
		if(y == pre || y == sp)continue;
		segind[y] = 0;
		segid[y] = ++ind;
		S[ind]++;
		who[ind].pb(y);
		dfs_hld(y, x);
	}
}

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

int ans(vector<ii>& arr){
	long long int ret = 0;
	for(int i = 0; i < C; i++){
		ii x = arr[i];
		ret += bit.query(x.first - 1) * (long long int)x.second;
		bit.modify(x.first, x.second);
	}
	for(int i = 0; i < C; i++){
		ii x = arr[i];
		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];
      compress(val);
      for(int i = 0; i < n - 1; i++){
      	int x, y;
      	cin >> x >> y;
      	adj[x].pb(y);
      	adj[y].pb(x);
      	Q[i] = {x, y};
      }
      dfs(1, 0);
      who[0].pb(1);
      dfs_hld(1, 0);

      for(int i = 0; i <= n && S[i] > 0; i++) build(seg[i], i);
      update(1, val[1]);
      for(int i = 0; i < n - 1; i++){
      	query(Q[i].first);
      	cout << ans(W) << "\n";
      	C = 0;
      	update(Q[i].second, val[Q[i].second]);
      }
}

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