Submission #201603

#TimeUsernameProblemLanguageResultExecution timeMemory
201603khulegubArranging Shoes (IOI19_shoes)C++14
100 / 100
116 ms19832 KiB
#include "shoes.h" #include <bits/stdc++.h> #define mp make_pair #define pb push_back #define xx first #define yy second #define ll(x) (x*2) + 1 #define rr(x) (x*2) + 2 using namespace std; typedef long long i64; int n; bool taken[200010]; int ft[200010]; int update(int x){ x++; while (x < n){ ft[x]++; x += x & (-x); } return 0; } int query(int x){ int ret = 0; while (x > 0){ ret += ft[x]; x -= x & (-x); } return ret; } int query(int l, int r){ l++; r++; return query(r) - query(l - 1); } vector<int> lefts[200010], rights[200010]; i64 count_swaps(std::vector<int> s) { i64 ans = 0LL; n = s.size(); for (int i = n - 1; i >= 0; i--){ if (s[i] < 0) lefts[abs(s[i])].pb(i); else rights[abs(s[i])].pb(i); } for (int i = 0; i < n; i++){ if (!taken[i]){ taken[i] = true; int other; if (s[i] < 0){ other = rights[abs(s[i])].back(); rights[abs(s[i])].pop_back(); lefts[abs(s[i])].pop_back(); } else{ other = lefts[abs(s[i])].back(); rights[abs(s[i])].pop_back(); lefts[abs(s[i])].pop_back(); ans++; } taken[other] = true; ans += other - i - 1; ans -= query(i + 1, other - 1); update(other); } } return ans; }
#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...