이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;
#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed
const size_t fTsize = 1 << 18;
class fenwickTree {
public:
vector<int> vl;
int N;
fenwickTree() { vl.resize(fTsize); }
int query(int t) {
int ret = 0;
while (t) ret += vl[t], t -= (t & -t);
return ret;
}
int query(int l, int r) { return query(r) - query(l - 1); }
void update(int t, int d = -1) {
while (t < fTsize) vl[t] += d, t += (t & -t);
}
};
i64 count_swaps(vector<int> s) {
int N = s.size() >> 1;
i64 ret = 0;
set<pi> st;
vector<pi> match;
for (int i = 0; i < 2 * N; i++) {
auto it = st.lower_bound({-s[i], 0});
if (it != st.end() && it->first == -s[i]) {
match.emplace_back(it->second, i);
st.erase(it);
} else {
st.insert({s[i], i});
}
}
sort(iterall(match));
auto fT = fenwickTree();
for (int i = 1; i <= 2 * N; i++) fT.update(i, 1);
for (auto [l, r] : match) {
ret += fT.query(++l, ++r);
ret -= 2;
if (s[l - 1] > s[r - 1]) ret += 1;
fT.update(l);
fT.update(r);
}
return ret;
}
컴파일 시 표준 에러 (stderr) 메시지
shoes.cpp: In member function 'void fenwickTree::update(int, int)':
shoes.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
37 | while (t < fTsize) vl[t] += d, t += (t & -t);
| ~~^~~~~~~~
# | 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... |