This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
long long noneg,k,b[1000005],curindex,cursum,n,a[1000005];
queue<long long>q[500005];
vector<long long>s;
void update(int ind,int value) {
for(int i=ind; i<=n; i+=i&(-i))
b[i]+=value;
}
int curs(int ind1) {
cursum=0;
for(int i=ind1; i>=1; i-=i&(-i))
cursum+=b[i];
return cursum;
}
long long count_swaps(std:: vector<int>s) { // *** !
int k;
long long ans=0; //***
noneg=100005; n=s.size();
for(k=0; k<s.size(); k++) a[k+1]=s[k];
for(k=1;k<=n;k++) update(k,1);
for(k=1; k<=n; k++)
if(q[a[k]+noneg].size()>0) {
curindex=q[a[k]+noneg].front();
q[a[k]+noneg].pop();
ans+=curs(k)-curs(curindex)-1;
if(a[k]<0) ans++;
update(k,-1);
update(curindex,1);
} else q[a[k]*(-1)+noneg].push(k);
return ans;
}
Compilation message (stderr)
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:30:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(k=0; k<s.size(); k++) a[k+1]=s[k];
~^~~~~~~~~
# | 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... |