| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 101041 | ecasdqina | Construction of Highway (JOI18_construction) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;
struct SegmentTree {
std::vector<i64> seg, lazy;
int sz = 1;
SegmentTree(int n) {
while(sz < n) sz <<= 1;
seg.assign(sz * 2 - 1, 0);
}
void add(int k, int x = 1) {
k += sz - 1;
seg[k] += x;
while(k) {
k = (k - 1) >> 1;
seg[k] = seg[2 * k + 1] + seg[2 * k + 2];
}
}
void update(int k, int x = 1) {
k += sz - 1;
seg[k] = x;
while(k) {
k = (k - 1) >> 1;
seg[k] = seg[2 * k + 1] + seg[2 * k + 2];
}
}
void add(
i64 get(int a, int b, int k, int l, int r) {
if(b <= l || r <= a) return 0;
if(a <= l && r <= b) return seg[k];
i64 L = get(a, b, 2 * k + 1, l, (l + r) >> 1);
i64 R = get(a, b, 2 * k + 2, (l + r) >> 1, r);
return L + R;
}
i64 get(int a, int b) {
return get(a, b, 0, 0, sz);
}
i64 operator[](int k) {
return seg[k + sz - 1];
}
};
int main() {
int n; scanf("%d", &n);
std::vector<int> c(n), a(n - 1), b(n - 1), latte;
std::vector<int> number(n, -1);
for(int i = 0; i < n; i++) {
scanf("%d", &c[i]);
latte.push_back(c[i]);
}
for(int i = 0; i < n - 1; i++) {
scanf("%d%d", &a[i], &b[i]);
a[i]--; b[i]--;
number[b[i]] = i;
}
sort(begin(latte), end(latte)); latte.erase(unique(begin(latte), end(latte)), end(latte));
std::function<int (int)> getIndex = [&](int v) {
return lower_bound(begin(latte), end(latte), v) - begin(latte);
};
//assert(n <= 4000);
std::vector<int> parent(n, -1);
for(int i = 0; i < n - 1; i++) {
i64 ans = 0;
int now = a[i];
SegmentTree seg(latte.size());
while(now != -1) {
int k = getIndex(c[now]);
ans += seg.get(0, k);
seg.add(k);
c[now] = c[b[i]];
now = parent[now];
}
parent[b[i]] = a[i];
printf("%lld\n", ans);
// for(auto v: c) cout << v << " "; cout << endl;
}
return 0;
}