제출 #298262

#제출 시각아이디문제언어결과실행 시간메모리
298262emil_physmathArranging Shoes (IOI19_shoes)C++17
45 / 100
140 ms21360 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; using llong = long long; #define BUGO(x) cerr << #x << " = " << x << '\n'; const int maxN = 200'005; int t[maxN * 4]; vector<int> chng; void Add(int v, int vl, int vr, int i, int val) { chng.push_back(v); if (vl == vr) { t[v] = val; return; } int vm = vl + (vr - vl) / 2; if (i <= vm) Add(v * 2, vl, vm, i, val); else Add(v * 2 + 1, vm + 1, vr, i, val); t[v] = t[v * 2] + t[v * 2 + 1]; } int Count(int v, int vl, int vr, int l, int r) { if (l > vr || vl > r) return 0; if (l <= vl && vr <= r) return t[v]; int vm = vl + (vr - vl) / 2; return Count(v * 2, vl, vm, l, r) + Count(v * 2 + 1, vm + 1, vr, l, r); } long long count_swaps(vector<int> a) { int n = a.size(); llong ans = 0; int l = 0, r = 0; vector<int> pos(n); for (int i = 0; i < n; ++i) if (a[i] < 0) pos[i] = l++ * 2; else pos[i] = r++ * 2 + 1; for (int i = 0; i < n; ++i) { ans += Count(1, 0, n - 1, pos[i], n - 1); Add(1, 0, n - 1, pos[i], 1); } 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...