제출 #529077

#제출 시각아이디문제언어결과실행 시간메모리
529077yungyaoConstruction of Highway (JOI18_construction)C++17
16 / 100
2070 ms1372 KiB
using namespace std; #include <iostream> #include <algorithm> #include <vector> #include <utility> #include <set> #include <map> #include <stack> #include <queue> typedef long long LL; typedef pair<int,int> pii; #define pb push_back #define mkp make_pair #define F first #define S second #define iter(x) x.begin(),x.end() #define REP(n) for (int __=n;__--;) #define REP0(i, n) for (int i=0;i<n;++i) #define REP1(i, n) for (int i=1;i<=n;++i) const int maxn = 1e5+10, mod = 0; const LL inf = 0; int v[maxn], f[maxn]; struct BIT{ int bit[maxn], n; void init(int _n){ n = _n; REP1(i, n) bit[i] = 0; } void mdf(int k){ for (;k<=n;k+=k&-k) ++bit[k]; } int query(int k){ int ret = 0; for (;k;k-=k&-k) ret += bit[k]; return ret; } }bit; LL inv(vector <int> &v){ int n = v.size(); vector <pii> v2(n); REP0(i, n) v2[i] = mkp(v[i], i+1); sort(iter(v2),[](pii a, pii b){return a.F != b.F ? a.F < b.F : a.S > b.S;}); bit.init(n); LL ans = 0; for (auto &[_, i]:v2){ ans += bit.query(i); bit.mdf(i); } return ans; } void solve(){ int n; cin >> n; REP1(i, n) cin >> v[i]; REP(n-1){ int a, b; cin >> a >> b; vector <int> arr; for (int at=a;at;at = f[at]) {arr.pb(v[at]); v[at] = v[b];} f[b] = a; cout << inv(arr) << '\n'; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...