Submission #1226679

#TimeUsernameProblemLanguageResultExecution timeMemory
1226679repsakArranging Shoes (IOI19_shoes)C++20
10 / 100
0 ms328 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; class SegmentTree{ public: int length = 1; vector<ll> st; void setup(vector<int>& values){ int N = values.size(); while(length < N) length *= 2; st.resize(2 * length); } void update(int l, int r, int tl, int tr, int k){ if(tl > r || tr < l) return; if(tl >= l && tr <= r){ st[k] += 1; return; } int mid = (tl + tr) / 2; update(l, r, tl, mid, k * 2); update(l, r, mid + 1, tr, k * 2 + 1); } ll query(int index){ index += length; ll sum = st[index]; for(int i = index / 2; i > 0; i /= 2){ sum += st[i]; } return sum; } }; long long count_swaps(vector<int> s) { int N = s.size(); map<int, set<int>> remain; map<int, int> counter; for(int i = 0; i < N; i++){ remain[s[i]].insert(i); } SegmentTree tree; tree.setup(s); ll sum = 0; for(int i = 0; i < N; i++){ if(s[i] < 0 && counter[abs(s[i])] > 0 || s[i] > 0 && counter[abs(s[i])] < 0){ int inc = s[i] > 0 ? 1 : -1; counter[abs(s[i])] += inc; continue; } int inc = s[i] > 0 ? 1 : -1; counter[abs(s[i])] += inc; int turn = *(remain[s[i]].begin()); int other = *(remain[-1 * s[i]].begin()); int additional = s[turn] > s[other] ? 1 : 0; int offset = abs(tree.query(turn) - tree.query(other)); int diff = abs(turn - other) - 1; tree.update(turn, other, 0, tree.length, 1); // Remove pair remain[s[i]].erase(remain[s[i]].begin()); remain[-1 * s[i]].erase(remain[-1 * s[i]].begin()); sum += additional + offset + diff; } return sum; } // #include "grader.cpp"
#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...