제출 #163828

#제출 시각아이디문제언어결과실행 시간메모리
163828Alexa2001Arranging Shoes (IOI19_shoes)C++17
50 / 100
1079 ms9592 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int Nmax = 1e5 + 5; int n; int F[Nmax], S[Nmax], a[Nmax], cnt[Nmax], sum_cnt[Nmax]; void norm() { int i; for(i=1; i<=n; ++i) if(a[i] > 0) ++sum_cnt[a[i]]; for(i=1; i<=n; ++i) sum_cnt[i] += sum_cnt[i-1], cnt[i] = 0; for(i=1; i<=n; ++i) if(a[i] > 0) { ++cnt[a[i]]; a[i] = sum_cnt[a[i] - 1] + cnt[a[i]]; S[a[i]] = i; } for(i=1; i<=n; ++i) cnt[i] = 0; for(i=1; i<=n; ++i) if(a[i] < 0) { a[i] *= -1; ++cnt[a[i]]; a[i] = sum_cnt[a[i] - 1] + cnt[a[i]]; F[a[i]] = i; } } class AIB { int a[Nmax]; int ub(int x) { return (x&(-x)); } public: void clear() { memset(a, 0, sizeof(a)); } int query(int x) { int ans = 0; for(; x <= n; x += ub(x)) ans += a[x]; return ans; } void update(int x) { for(; x; x -= ub(x)) a[x] ++; } void update(int x, int y) { for(; x; x-=ub(x)) a[x] --; for(; y; y-=ub(y)) a[y] ++; } } aib; ll solve1() { ll ans = 0; int i; aib.clear(); for(i=1; i<=n; ++i) if(i == max(F[a[i]], S[a[i]])) { int curr = min(F[a[i]], S[a[i]]); ans += 2 * aib.query(curr); aib.update(curr); } aib.clear(); for(i=1; i<=n; ++i) if(i == max(F[a[i]], S[a[i]])) { int curr = min(F[a[i]], S[a[i]]); ans += aib.query(curr); aib.update(curr, i); } return ans; } ll solve2() { int i, ans = 0; for(i=1; i<=n; ++i) ans += (F[i] > S[i]); return ans; } ll count_swaps(vector<int> s) { n = s.size(); int i; for(i=1; i<=n; ++i) a[i] = s[i-1]; norm(); // for(i=1; i<=n; ++i) cerr << a[i] << ' '; cerr << "#\n"; // cerr << solve1() << '\n'; // cerr << solve2() << '\n'; return solve1() + solve2(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...