| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 47400 | daniel_02 | Construction of Highway (JOI18_construction) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
using namespace std;
const int N = 4000 + 7;
const int inf = 1e9 + 7;
int a[N], pr[N];
struct con
{
int l, r;
ll sm;
con()
{
l = r = sm = 0;
}
}t[N * 7];
int cnt;
void update(int v, int tl, int tr, int pos, int x)
{
if (tl == tr)
{
t[v].sm = max(t[v].sm + x, 0LL);
}
else
{
int mid = (tl + tr) >> 1;
if (mid >= pos)
{
if (!t[v].l)
t[v].l = ++cnt;
update(t[v].l, tl, mid, pos, x);
}
else
{
if (!t[v].r)
t[v].r = ++cnt;
update(t[v].r, mid + 1, tr, pos, x);
}
if (!t[v].l)t[v].l = ++cnt;
if (!t[v].r)t[v].r = ++cnt;
t[v].sm = t[t[v].l].sm + t[t[v].r].sm;
}
}
ll get(int v, int tl, int tr, int l, int r)
{
if (tl > r || l > tr)return 0LL;
if (l <= tl && tr <= r)
{
return t[v].sm;
}
else
{
int mid = (tl + tr) >> 1;
if (!t[v].l)
t[v].l = ++cnt;
if (!t[v].r)
t[v].r = ++cnt;
return get(t[v].l, tl, mid, l, r) + get(t[v].r, mid + 1, tr, l, r);
}
}
deque<int>dq;
void dfs(int v)
{
if (v == 0)
return;
dq.pf(a[v]);
dfs(pr[v]);
}
void conquer(int v)
{
ll ans = 0;
dfs(v);
cnt = 1;
for (int i = 0; i < dq.size(); i++)
{
ans += get(1, 1, inf, dq[i] + 1, inf);
update(1, 1, inf, dq[i], 1);
}
// for (int i = 0; i < dq.size(); i++)
// update(1, 1, inf, dq[i], -inf);
memset(t, 0, sizeof(t));
dq.clear();
printf("%lld\n", ans);
}
void upd(int v, int x)
{
if (v == 0)return;
a[v] = x;
upd(pr[v], x);
}
main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i < n; i++)
{
int q, w;
scanf("%d%d", &q, &w);
if (i == 1)
{
puts("0");
pr[w] = q;
a[q] = a[w];
continue;
}
conquer(q);
upd(q, a[w]);
pr[w] = q;
}
}
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
using namespace std;
const int N = 4000 + 7;
const int inf = 1e9 + 7;
int a[N], pr[N];
struct con
{
int l, r;
ll sm;
con()
{
l = r = sm = 0;
}
}t[N * 7];
int cnt;
void update(int v, int tl, int tr, int pos, int x)
{
if (tl == tr)
{
t[v].sm = max(t[v].sm + x, 0LL);
}
else
{
int mid = (tl + tr) >> 1;
if (mid >= pos)
{
if (!t[v].l)
t[v].l = ++cnt;
update(t[v].l, tl, mid, pos, x);
}
else
{
if (!t[v].r)
t[v].r = ++cnt;
update(t[v].r, mid + 1, tr, pos, x);
}
if (!t[v].l)t[v].l = ++cnt;
if (!t[v].r)t[v].r = ++cnt;
t[v].sm = t[t[v].l].sm + t[t[v].r].sm;
}
}
ll get(int v, int tl, int tr, int l, int r)
{
if (tl > r || l > tr)return 0LL;
if (l <= tl && tr <= r)
{
return t[v].sm;
}
else
{
int mid = (tl + tr) >> 1;
if (!t[v].l)
t[v].l = ++cnt;
if (!t[v].r)
t[v].r = ++cnt;
return get(t[v].l, tl, mid, l, r) + get(t[v].r, mid + 1, tr, l, r);
}
}
deque<int>dq;
void dfs(int v)
{
if (v == 0)
return;
dq.pf(a[v]);
dfs(pr[v]);
}
void conquer(int v)
{
ll ans = 0;
dfs(v);
cnt = 1;
for (int i = 0; i < dq.size(); i++)
{
ans += get(1, 1, inf, dq[i] + 1, inf);
update(1, 1, inf, dq[i], 1);
}
// for (int i = 0; i < dq.size(); i++)
// update(1, 1, inf, dq[i], -inf);
memset(t, 0, sizeof(t));
dq.clear();
printf("%lld\n", ans);
}
void upd(int v, int x)
{
if (v == 0)return;
a[v] = x;
upd(pr[v], x);
}
main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i < n; i++)
{
int q, w;
scanf("%d%d", &q, &w);
if (i == 1)
{
puts("0");
pr[w] = q;
a[q] = a[w];
continue;
}
conquer(q);
upd(q, a[w]);
pr[w] = q;
}
}