이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <map>
using namespace std;
const int maxn = 2e5 + 5;
long long T[maxn*4];
void update (int v, int tl, int tr, int pos, int val){
if(tl == tr){
T[v] += val;
return;
}
int tm = (tl + tr) >> 1;
if(pos <= tm)
update(v + v, tl, tm, pos, val);
else
update(v + v +1, tm + 1, tr, pos, val);
T[v] = T[v + v] + T[v + v + 1];
}
long long get(int v, int tl, int tr, int l, int r){
if(l > r) return 0ll;
if(tl == l && tr == r){
return T[v];
}
int tm = (tl + tr) >> 1;
return get(v + v, tl, tm, l, min (r, tm)) + get(v + v + 1, tm + 1, tr, max(l, tm + 1), r);
}
map <int, deque<int>> pos;
long long count_swaps(vector<int> S){
for(int i = 0; i < S.size(); i++){
pos[S[i]].push_back(i);
}
long long swaps = 0ll;
vector <int> ok(S.size(), 0);
for(int i = 0; i < S.size(); i++){
if(ok[i])continue;
deque <int>&NegPos = pos[-S[i]];
int negPos = NegPos.front();
pos[S[i]].pop_front();
NegPos.pop_front();
swaps += negPos - get(1, 0, S.size()-1, i, negPos) - i;
update(1, 0, S.size() - 1, negPos, 1);
ok[negPos] = 1;
if(S[i] < 0)
swaps--;
}
return swaps;
}
#ifdef RAFFF
int main(){
vector <int> a(4);
a[0] = 2; a[1] = 1; a[2] = -1; a[3] = -2;
int i;
cout << count_swaps(a) << '\n';
cin >> i;
return 0;
}
#endif
컴파일 시 표준 에러 (stderr) 메시지
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < S.size(); i++){
~~^~~~~~~~~~
shoes.cpp:46:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < S.size(); i++){
~~^~~~~~~~~~
# | 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... |