Submission #373614

#TimeUsernameProblemLanguageResultExecution timeMemory
373614SnowFlake7Arranging Shoes (IOI19_shoes)C++14
100 / 100
277 ms207724 KiB
#include <bits/stdc++.h> #include "shoes.h" using namespace std; queue <int> q[300005]; int v[300005],aib[300005],n; long long s; void update(int poz, int val) { for (int i = poz;i <= n;i += i&(-i)) aib[i] += val; } long long query(int poz) { s = 0; for (int i = poz;i > 0;i -= i&(-i)) s += aib[i]; return s; } int f(int x) { if (x > 0) return x + n; else return -x; } long long count_swaps(vector<int> s) { long long ans = 0,a; n = s.size(); for (int i = 0;i < n;i++) { v[i + 1] = s[i]; q[f(v[i + 1])].push(i + 1); update(i + 1, 1); } for (int i = 1;i <= n;i++) { if (q[f(v[i])].front() != i) continue; q[f(v[i])].pop(); if (v[i] < 0) update(i, -1); a = q[f(-v[i])].front(); q[f(-v[i])].pop(); update(a, -1); ans += query(a); if (v[i] > 0) update(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...