이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
template<class T> bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
constexpr int dy[4]={-1,0,1,0};
constexpr int dx[4]={0,-1,0,1};
template<typename T>
struct SegmentTree{
private:
int n, N;
vector<T> node;
function<T(T, T)> F;
T E;
public:
void init(int _n, function<T(T, T)> f, T e){
F = f;
E = e;
n = _n;
N = 1;
while(N < n) N = (N<<1);
node.assign(2*N-1, e);
}
void init(vector<T> v, function<T(T, T)> f, T e){
F = f;
E = e;
n = v.size();
N = 1;
while(N < n) N = (N<<1);
node.assign(2*N-1, e);
for(int i=0; i<n; i++) node[N-1+i] = v[i];
for(int i=N-2; i>=0; i--) node[i] = F(node[(i<<1)+1], node[(i<<1)+2]);
}
T& operator [](int a){
return node[N-1+a];
}
void update(int a, T x){
a += N-1;
node[a] = x;
while(a > 0){
a = (a-1)>>1;
node[a] = F(node[(a<<1)+1], node[(a<<1)+2]);
}
}
T query(int a, int b, int k=0, int l=0, int r=-1){
if(r == -1) r = N;
if(b <= l || r <= a) return E;
if(a <= l && r <= b) return node[k];
return F(query(a, b, (k<<1)+1, l, (l+r)>>1), query(a, b, (k<<1)+2, (l+r)>>1, r));
}
int find_right(function<bool(T)> g, int a){
if(!g(E)) return -1;
T t = E;
return min(find_right(g, a, 0, 0, N, t), n);
}
int find_right(function<bool(T)> g, int a, int k, int l, int r, T &t){
if(r-l == 1){
t = F(t, node[k]);
return g(t) ? r : a;
}
int m = (l + r) >> 1;
if(m <= a) return find_right(g, a, (k<<1)+2, m, r, t);
if(a <= l && g(F(t, node[k]))){
t = F(t, node[k]);
return r;
}
int L = find_right(g, a, (k<<1)+1, l, m, t);
if(L < m) return L;
int R = find_right(g, a, (k<<1)+2, m, r, t);
return max(L, R);
}
int find_left(function<bool(T)> g, int b){
if(!g(E)) return n + 1;
T t = E;
return find_left(g, b, 0, 0, N, t);
}
int find_left(function<bool(T)> g, int b, int k, int l, int r, T t){
if(r-l == 1){
t = F(node[k], t);
return g(t) ? l : b;
}
int m = (l + r) >> 1;
if(b <= m) return find_left(g, b, (k<<1)+1, l, m, t);
if(r <= b && g(F(node[k], t))){
t = F(node[k], t);
return l;
}
int R = find_left(g, b, (k<<1)+2, m, r, t);
if(m < R) return R;
int L = find_left(g, b, (k<<1)+1, l, m, t);
return min(L, R);
}
};
int N;
int C[100000];
int A[100000], B[100000];
vector<int> z;
int par[100000] ={-1};
vector<int> chi[100000];
int s[100000] ={};
int siz(int v){
if(s[v] != 0) return s[v];
s[v] = 1;
for(int i=0; i<chi[v].size(); i++) s[v] += siz(chi[v][i]);
return s[v];
}
int d[100000] ={};
int depth(int v){
if(d[v] != 0) return d[v];
if(par[v] == -1) return 0;
return d[v] = 1 + depth(par[v]);
}
vector<int> hld;
int pre[100000];
int top[100000];
void HLD(int v, int a){
pre[v] = hld.size();
hld.pb(v);
top[v] = a;
if(chi[v].size() == 0) return;
int M = 0;
int idx = -1;
for(int i=0; i<chi[v].size(); i++){
if(chmax(M, siz(chi[v][i]))) idx = i;
}
HLD(chi[v][idx], a);
for(int i=0; i<chi[v].size(); i++){
if(i != idx) HLD(chi[v][i], chi[v][i]);
}
}
vector<pair<int, int>> query(int v){ // [,]
vector<pair<int, int>> ret;
while(v != -1){
ret.pb({pre[top[v]], pre[v]});
v = par[top[v]];
}
reverse(all(ret));
return ret;
}
struct range{
int l, r, a;
};
stack<range> st[100000];
SegmentTree<ll> segtree;
signed main(){
scanf("%d", &N);
rep(i, N){
scanf("%d", C+i);
z.pb(C[i]);
}
sort(all(z));
rep(i, N) C[i] = lower_bound(all(z), C[i]) - z.begin();
rep(i, N-1){
scanf("%d%d", A+i, B+i);
A[i]--; B[i]--;
par[B[i]] = A[i];
chi[A[i]].pb(B[i]);
}
HLD(0, 0);
st[0].push({0,0,C[0]});
segtree.init(N, [](ll a, ll b){ return a+b; }, 0);
rep(i, N-1){
ll ans = 0;
auto v = query(B[i]);
vector<int> memo;
rep(j, v.size()){
while(st[v[j].first].size() > 0 && st[v[j].first].top().l <= v[j].second){ // O(N log N)
range r = st[v[j].first].top();
st[v[j].first].pop();
if(v[j].second < r.r){
st[v[j].first].push({v[j].second+1, r.r, r.a});
r.r = v[j].second;
}
ans += segtree.query(r.a+1, N) * (ll)(r.r - r.l + 1);
segtree.update(r.a, segtree[r.a] + r.r - r.l + 1);
memo.pb(r.a);
}
st[v[j].first].push({v[j].first, v[j].second, C[B[i]]});
}
printf("%lld\n", ans);
rep(j, memo.size()) segtree.update(memo[j], 0);
}
}
컴파일 시 표준 에러 (stderr) 메시지
construction.cpp: In function 'int siz(int)':
construction.cpp:120:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for(int i=0; i<chi[v].size(); i++) s[v] += siz(chi[v][i]);
| ~^~~~~~~~~~~~~~
construction.cpp: In function 'void HLD(int, int)':
construction.cpp:142:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for(int i=0; i<chi[v].size(); i++){
| ~^~~~~~~~~~~~~~
construction.cpp:146:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for(int i=0; i<chi[v].size(); i++){
| ~^~~~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
construction.cpp:171:5: note: in expansion of macro 'rep'
171 | rep(i, N){
| ^~~
construction.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
construction.cpp:176:5: note: in expansion of macro 'rep'
176 | rep(i, N) C[i] = lower_bound(all(z), C[i]) - z.begin();
| ^~~
construction.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
construction.cpp:177:5: note: in expansion of macro 'rep'
177 | rep(i, N-1){
| ^~~
construction.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
construction.cpp:188:5: note: in expansion of macro 'rep'
188 | rep(i, N-1){
| ^~~
construction.cpp:15:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
construction.cpp:192:9: note: in expansion of macro 'rep'
192 | rep(j, v.size()){
| ^~~
construction.cpp:15:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ~~~^~~~
construction.cpp:192:9: note: in expansion of macro 'rep'
192 | rep(j, v.size()){
| ^~~
construction.cpp:15:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
construction.cpp:207:9: note: in expansion of macro 'rep'
207 | rep(j, memo.size()) segtree.update(memo[j], 0);
| ^~~
construction.cpp:15:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ~~~^~~~
construction.cpp:207:9: note: in expansion of macro 'rep'
207 | rep(j, memo.size()) segtree.update(memo[j], 0);
| ^~~
construction.cpp:170:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
170 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
construction.cpp:172:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
172 | scanf("%d", C+i);
| ~~~~~^~~~~~~~~~~
construction.cpp:178:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
178 | scanf("%d%d", A+i, B+i);
| ~~~~~^~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |