제출 #298268

#제출 시각아이디문제언어결과실행 시간메모리
298268emil_physmathArranging Shoes (IOI19_shoes)C++17
10 / 100
1091 ms384 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(); if (n <= 16) { llong ans = 0; while (true) { int j = -1; for (int i = 0; i < n; i += 2) if (abs(a[i]) != abs(a[i + 1]) || a[i] > 0 || a[i + 1] < 0) { j = i; break; } if (j == -1) break; int i = j + 1; while (abs(a[i]) != abs(a[j])) { ++i; if (i >= n) exit(0); } while (i > j + 1) { ++ans; swap(a[i - 1], a[i]); --i; } if (a[j] > 0) { swap(a[j], a[j + 1]); ++ans; } } return ans; } 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...