| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 478377 | tranxuanbach | Construction of Highway (JOI18_construction) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define FordE(i, l, r) for (int i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;
const int N = 1e5 + 5, mod = 1e9 + 7;
struct lazy_segment_tree_sum{
int seg[1 << 18], lazy[1 << 18];
void down(int id){
if (lazy[id]){
seg[id * 2] = seg[id * 2 + 1] = 0;
lazy[id * 2] = lazy[id * 2 + 1] = 1;
lazy[id] = 0;
}
}
void reset(){
lazy[1] = 1;
}
void update(int id, int l, int r, int i, int val){
if (l == r){
seg[id] += val;
return;
}
down(id);
int mid = (l + r) >> 1;
if (i <= mid){
update(id * 2, l, mid, i, val);
}
else{
update(id * 2 + 1, mid + 1, r, i, val);
}
seg[id] = seg[id * 2] + seg[id * 2 + 1];
}
int get(int id, int l, int r, int u, int v){
if (v < l or r < u){
return 0;
}
if (u <= l and r <= v){
return seg[id];
}
down(id);
int mid = (l + r) >> 1;
return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
}
} segval;
struct lazy_chain{
struct node{
int val, chainbegin, chainend, child;
node(){
}
node(int val, int chainbegin, int chainend, int child = 0): val(val), chainbegin(chainbegin), chainend(chainend), child(child){
}
};
node seg[1 << 18];
void build(int id, int l, int r, int aval[]){
if (l == r){
seg[id] = node(aval[tour[l]], tour[l], tour[l]);
return;
}
int mid = (l + r) >> 1;
build(id * 2, l, mid, aval);
build(id * 2 + 1, mid + 1, r, aval);
}
node getnode(int id, int l, int r, int i){
if (l == r){
return seg[id];
}
int mid = (l + r) >> 1;
if (i <= mid){
return getnode(id * 2, l, mid);
}
else{
return getnode(id * 2 + 1, mid + 1, r);
}
}
} segchain;
int n;
int a[N];
pii aquery[N];
vi adj[N];
int par[N];
int h[N], sz[N];
int ctrtour, tour[N], tin[N], tout[N];
int nxt[N];
void dfs_sz(int u){
sz[u] = 1;
Fora(&v, adj[u]){
h[v] = h[u] + 1;
dfs_sz(v);
sz[u] += sz[v];
if (sz[v] > sz[adj[u][0]]){
swap(v, adj[u][0]);
}
}
}
void dfs_tour(int u){
tour[++ctrtour] = u;
tin[u] = ctrtour;
Fora(v, adj[u]){
nxt[v] = (v == adj[u][0] ? nxt[u] : v);
dfs_tour(v);
}
tout[u] = ctrtour;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("KEK.inp", "r", stdin);
// freopen("KEK.out", "w", stdout);
cin >> n;
ForE(i, 1, n){
cin >> a[i];
}
For(i, 1, n){
cin >> aquery[i].fi >> aquery[i].se;
}
{
int ctrmpp = 0; map <int, int> mpp;
ForE(i, 1, n){
mpp[a[i]] = 1;
}
Fora(&elem, mpp){
elem.se = ++ctrmpp;
}
ForE(i, 1, n){
a[i] = mpp[a[i]];
}
}
{
For(i, 1, n){
adj[aquery[i].fi].emplace_back(aquery[i].se);
par[aquery[i].se] = aquery[i].fi;
}
dfs_sz(1);
nxt[1] = 1;
dfs_tour(1);
}
segchain.build(1, 1, n, a);
For(i, 1, n){
int u = aquery[i].fi, v = aquery[i].se;
{
ll ans = 0;
segval.reset();
while (u){
auto nodeu = segchain.getnode(1, 1, n, tin[u]);
ans += (ll)segval.get(1, 1, n, 1, nodeu.val - 1) * (h[u] - h[nodeu.chainbegin] + 1);
segval.update(1, 1, n, nodeu.val, h[u] - h[nodeu.chainbegin] + 1);
u = par[nodeu.chainbegin];
}
cout << ans << endl;
}
u = aquery[i].fi;
{
while (u){
auto nodeu = segchain.getnode(1, 1, n, tin[u]);
}
}
}
}
/*
==================================================+
INPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/