# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
143549 | abeker | Arranging Shoes (IOI19_shoes) | C++17 | 208 ms | 70108 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
struct fenwick {
vector <int> fen;
fenwick(int n) {
fen.resize(n + 5);
}
void update(int x) {
for (x++; x < fen.size(); x += x & -x)
fen[x]++;
}
int get(int x) {
int res = 0;
for (x++; x; x -= x & -x)
res += fen[x];
return res;
}
};
int N;
vector <int> lft[MAXN], rig[MAXN];
vector <int> perm[MAXN], pos[MAXN];
ll inversions(vector <int> v) {
reverse(v.begin(), v.end());
fenwick tmp(v.size());
ll res = 0;
for (auto it : v) {
res += tmp.get(it);
tmp.update(it);
}
return res;
}
ll count_swaps(vector <int> shoes) {
N = shoes.size();
vector <int> todo(N, -1);
for (int i = 0; i < N; i++) {
int sz = abs(shoes[i]);
if (shoes[i] < 0) {
perm[sz].push_back(2 * lft[sz].size());
lft[sz].push_back(i);
}
else {
perm[sz].push_back(2 * rig[sz].size() + 1);
rig[sz].push_back(i);
}
pos[sz].push_back(i);
}
ll sol = 0;
for (int i = 0; i < N; i++) {
sol += inversions(perm[i]);
for (int j = 0; j < lft[i].size(); j++)
todo[max(lft[i][j], rig[i][j])] = min(lft[i][j], rig[i][j]);
}
fenwick fin(N);
for (int i = 0; i < N; i++)
if (todo[i] != -1) {
sol += fin.get(N) - fin.get(todo[i]);
fin.update(todo[i]);
fin.update(i);
}
for (int i = 0; i < N; i++) {
fenwick tmp(pos[i].size());
for (auto it : pos[i])
if (todo[it] != -1) {
sol -= tmp.get(pos[i].size()) - tmp.get(todo[it]);
tmp.update(todo[it]);
tmp.update(it);
}
}
return sol;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |