제출 #212339

#제출 시각아이디문제언어결과실행 시간메모리
212339jk89Arranging Shoes (IOI19_shoes)C++14
0 / 100
99 ms135032 KiB
#include <cstdio> #include <algorithm> #include <vector> #include <queue> using namespace std; #define f first #define s second const int MAXN = 1e5 + 3; const int MAXM = 512 * 1024 + 3; int tree[MAXM]; deque<int> q[MAXN]; deque<int> q2[MAXN]; long long ret; long long suma(int v) { ret = 0; while (v) { ret += tree[v]; v /= 2; } return ret; } void dodaj(int v, int x, int y, int a, int b) { if (y < a || x > b) return; if (x >= a && y <= b) { tree[v]++; return; } dodaj(v * 2, x, (x + y) / 2, a, b); dodaj(v * 2 + 1, (x + y) / 2 + 1, y, a, b); } long long count_swaps(vector<int> v) { long long ans = 0, temp; int n = v.size(); int x, y, pot = 1; while (pot < n) pot *= 2; for (int i = 1; i <= n; i++) { x = v[i - 1]; if (x < 0) { x = -x; if (q[x].empty()) { q2[x].push_back(i); continue; } y = q[x].front(); q[x].pop_front(); temp = x - y + 1 - suma(y + pot - 1); dodaj(1, 1, pot, y, x); ans += temp + 1; } else { if (q2[x].empty()) { q[x].push_back(i); continue; } y = q2[x].front(); q2[x].pop_front(); temp = x - y + 1 - suma(y + pot - 1); dodaj(1, 1, pot, y, x); ans += temp; } } 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...