제출 #924955

#제출 시각아이디문제언어결과실행 시간메모리
924955hmm789Arranging Shoes (IOI19_shoes)C++17
100 / 100
72 ms22812 KiB
#include <bits/stdc++.h> using namespace std; #define INF 1000000000000000000 #define MOD 998244353 int fw[200005]; void update(int x, int v) { for(x++; x < 200005; x += x&-x) fw[x] += v; } int query(int x) { int ans = 0; for(x++; x; x -= x&-x) ans += fw[x]; return ans; } int query(int x, int y) { return query(y)-query(x-1); } long long count_swaps(std::vector<int> s) { long long ans = 0; int n = (int)s.size()/2; set<int> nxt[2*n+1]; for(int i = 0; i < 2*n; i++) { nxt[s[i]+n].insert(i); } for(int i = 0; i < 2*n; i++) { if(query(i, i)) continue; int p = *nxt[-s[i]+n].begin(); nxt[-s[i]+n].erase(nxt[-s[i]+n].begin()); nxt[s[i]+n].erase(nxt[s[i]+n].begin()); ans += p-i - query(i, p) - (s[i] < 0); update(i, 1); update(p, 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...