Submission #170679

#TimeUsernameProblemLanguageResultExecution timeMemory
170679youngyojunArranging Shoes (IOI19_shoes)C++17
45 / 100
62 ms13360 KiB
#include "shoes.h" #include <bits/stdc++.h> #define eb emplace_back #define sz(V) ((int)(V).size()) #define allv(V) ((V).begin()),((V).end()) #define rb(x) ((x)&(-(x))) #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int, int> pii; const int MAXN = 200055; struct BIT { int d[MAXN]; void upd(int x, int r) { for(x += 5; x < MAXN; x += rb(x)) d[x] += r; } int get(int x) { int r = 0; for(x += 5; x; x -= rb(x)) r += d[x]; return r; } } bit; vector<int> BV[MAXN]; vector<pii> AV; int A[MAXN]; ll Ans; int N; ll solve() { for(int i = 0; i < N*2; i++) { if(A[i] > 0) BV[A[i]].eb(i); else AV.eb(-A[i], i); } for(int i = 1; i <= N; i++) reverse(allv(BV[i])); for(int i = 0, x = 0, y; i < N; i++, x += 2) { y = AV[i].fi; Ans += x - AV[i].se + i*2 - bit.get(AV[i].se); bit.upd(AV[i].se, 1); Ans += x+1 - BV[y].back() + i*2+1 - bit.get(BV[y].back()); bit.upd(BV[y].back(), 1); BV[y].pop_back(); } return Ans; } long long count_swaps(std::vector<int> s) { N = sz(s)/2; for(int i = 0; i < N*2; i++) A[i] = s[i]; return solve(); }
#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...