이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
int n,pos[200005],now,pt;
long long ans;
queue <int> v[200005];
vector <int> ct,d;
void cntInv(int l,int r){
if (l == r);
else
{
int mid=(l+r)/2;
ct.clear(); d.clear();
for (int i=l;i<=mid;i++){
ct.push_back(pos[i]);
}
sort(ct.begin(),ct.end()); reverse(ct.begin(),ct.end());
for (int i=mid+1;i<=r;i++){
d.push_back(pos[i]);
}
sort(d.begin(),d.end()); reverse(d.begin(),d.end());
pt=0;
for (int i=0;i<d.size();i++){
while (pt < (int)ct.size() && ct[pt] >= d[i])
pt++;
ans+=pt;
}
cntInv(l,mid);
cntInv(mid+1,r);
}
}
long long count_swaps(std::vector<int> s) {
n=(long long)s.size();
for (int i=0;i<n;i++){
if (v[100000-s[i]].empty())
v[s[i]+100000].push(i);
else
{
if (s[v[100000-s[i]].front()] < 0){
pos[v[100000-s[i]].front()]=now;
pos[i]=now+1;
}
else
{
pos[v[100000-s[i]].front()]=now+1;
pos[i]=now;
}
now+=2;
v[100000-s[i]].pop();
}
}
cntInv(0,n-1);
return ans;
}
/*int r,x;
vector <int> ori;
int main(){
cin >> r;
for (int i=0;i<2*r;i++){
cin >> x;
ori.push_back(x);
}
cout << count_swaps(ori) << "\n";
}*/
컴파일 시 표준 에러 (stderr) 메시지
shoes.cpp: In function 'void cntInv(int, int)':
shoes.cpp:25:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for (int i=0;i<d.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... |