제출 #961330

#제출 시각아이디문제언어결과실행 시간메모리
961330Ice_manConstruction of Highway (JOI18_construction)C++14
100 / 100
743 ms35932 KiB
/** ____ ____ ____ __________________ ____ ____ ____ ||I || ||c || ||e || || || ||M || ||a || ||n || ||__|| ||__|| ||__|| ||________________|| ||__|| ||__|| ||__|| |/__\| |/__\| |/__\| |/________________\| |/__\| |/__\| |/__\| */ #include <iostream> #include <chrono> #include <algorithm> #include <map> #include <vector> #define maxn 200005 #define maxlog 20 #define INF 1000000010 #define LINF 1000000000000000005 #define endl '\n' #define pb(x) push_back(x) #define X first #define Y second #define control cerr<<"passed"<<endl; //#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math") //#pragma GCC target("avx2") using namespace std; /**std::chrono::high_resolution_clock::time_point startT, currT; constexpr double TIME_MULT = 1; double timePassed() { using namespace std::chrono; currT = high_resolution_clock::now(); double time = duration_cast<duration<double>>(currT - startT).count(); return time * TIME_MULT; }*/ typedef pair <int , int> pii; pii _merge(pii e1 , pii e2) { return {min(e1.X , e2.X) , max(e1.Y , e2.Y)}; } int n; vector <int> v[maxn]; int c[maxn]; int pom; int x[maxn] , y[maxn]; void read() { pom = 0; cin >> n; for(int i = 1; i <= n; i++) cin >> c[i]; vector <int> sorted; for(int i = 1; i <= n; i++) sorted.pb(c[i]); sort(sorted.begin() , sorted.end()); map <int , int> id; for(int i = 0; i < sorted.size(); i++) { if(i == 0) pom++; if(i != 0 && sorted[i] != sorted[i - 1]) pom++; id[sorted[i]] = pom; } for(int i = 1; i <= n; i++) c[i] = id[c[i]]; for(int i = 1; i < n; i++) { cin >> x[i] >> y[i]; v[x[i]].pb(y[i]); v[y[i]].pb(x[i]); } } int lazy[maxn * 4]; pii tree[maxn * 4]; void push(int node) { if(lazy[node] == 0) return; tree[node * 2].X = lazy[node]; tree[node * 2].Y = lazy[node]; tree[node * 2 + 1].X = lazy[node]; tree[node * 2 + 1].Y = lazy[node]; lazy[node * 2] = lazy[node]; lazy[node * 2 + 1] = lazy[node]; lazy[node] = 0; } pii query(int node , int l , int r , int ql , int qr) { if(ql > qr) return {1e9 , 0}; if(ql == l && qr == r) return tree[node]; push(node); int mid = (l + r) / 2; int new_l = max(mid + 1 , ql); int new_r = min(mid , qr); pii res1 = query(node * 2 , l , mid , ql , new_r); pii res2 = query(node * 2 + 1 , mid + 1 , r , new_l , qr); return _merge(res1 , res2); } void update(int node , int l , int r , int ql , int qr , int qval) { if(ql > qr) return; if(ql == l && qr == r) { tree[node].X = qval; tree[node].Y = qval; lazy[node] = qval; return; } push(node); int mid = (l + r) / 2; int new_l = max(mid + 1 , ql); int new_r = min(mid , qr); update(node * 2 , l , mid , ql , new_r , qval); update(node * 2 + 1 , mid + 1 , r , new_l , qr , qval); tree[node] = _merge(tree[node * 2] , tree[node * 2 + 1]); } int fenwick[maxn]; void update_fenwick(int idx , int qval) { for(int i = idx; i <= pom; i += (i & (-i))) fenwick[i] += qval; } int query_fenwick(int idx) { int ans = 0; for(int i = idx; i >= 1; i -= (i & (-i))) ans += fenwick[i]; return ans; } vector <pii> _try; void new_segment(int from , int to) { int l , r , mid; while(from <= to) { l = from - 1; r = to; while(l + 1 < r) { mid = (l + r) / 2; pii pomm = query(1 , 1 , n , mid , to); if(pomm.X == pomm.Y) r = mid; else l = mid; } pii pomm = query(1 , 1 , n , r , to); _try.push_back({pomm.X , to - r + 1}); to = r - 1; } } int par[maxn]; int depth[maxn]; int sz[maxn]; int h[maxn]; void dfs(int node , int _par = 0 , int de = 1) { sz[node] = 1; depth[node] = de; par[node] = _par; for(int nb : v[node]) { if(nb == _par) continue; dfs(nb , node , de + 1); if(sz[nb] > sz[h[node]]) h[node] = nb; sz[node] += sz[nb]; } } int idx; int pp[maxn]; int lead[maxn]; void hld(int node , int _par = 0 , int head = 1) { lead[node] = head; idx++; pp[node] = idx; if(h[node] != 0) hld(h[node] , node , head); for(int nb : v[node]) { if(nb == _par) continue; if(nb == h[node]) continue; hld(nb , node , nb); } } void solve() { //control dfs(1); //control hld(1); for(int i = 1; i <= n; i++) update(1 , 1 , n , pp[i] , pp[i] , c[i]); long long inv = 0; for(int i = 1; i < n; i++) { //control inv = 0; _try.clear(); int node = x[i]; while(node) { new_segment(pp[lead[node]] , pp[node]); node = par[lead[node]]; } for(pii e : _try) { inv += query_fenwick(e.X - 1) * 1LL * e.Y; update_fenwick(e.X , e.Y); } for(pii e : _try) update_fenwick(e.X , -e.Y); node = y[i]; while(node) { update(1 ,1 , n , pp[lead[node]] , pp[node] , c[y[i]]); node = par[lead[node]]; } cout << inv << endl; } } int main() { /**#ifdef ONLINE_JUDGE /// promeni freopen("taxi.in", "r", stdin); freopen("taxi.out", "w", stdout); #endif*/ ios_base::sync_with_stdio(false); cin.tie(nullptr); //startT = std::chrono::high_resolution_clock::now(); read(); solve(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

construction.cpp: In function 'void read()':
construction.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i = 0; i < sorted.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...