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 "shoes.h"
#include <bits/stdc++.h>
using namespace std;
int n;
map<int,stack<int>> h;
bool vs[200005];
int st[1000005],lz[1000005];
void upd(int no,int i,int f,int pos)
{
if (f<pos) return;
if (i<pos) {
int l,r;
l = no*2+1;
r = l+1;
lz[l] += lz[no];
lz[r] += lz[no];
lz[no] = 0;
int m = (i+f)/2;
upd(l,i,m,pos);
upd(r,m+1,f,pos);
return;
} else {
lz[no]++;
return;
}
}
int get(int no,int i,int f,int pos)
{
if (f<pos || i>pos) return 0;
if (i==f) {
return lz[no];
}
int m = (i+f)/2;
int l,r;
l = no*2+1;
r = l+1;
lz[l] += lz[no];
lz[r] += lz[no];
lz[no] =0;
return get(l,i,m,pos)+get(r,m+1,f,pos);
}
long long count_swaps(vector<int> s) {
n = s.size()/2;
long long k=0;
for (int i=0;i<n+n;i++)
h[s[i]].push(i);
for (int i=n+n-1;i>=0;i--) if (!vs[i]) {
h[s[i]].pop();
int p = h[s[i]*-1].top();
h[s[i]*-1].pop();
int p1,p2;
// change the res[p] to get(0,0,n+n,p);
p1 = p-get(0,0,n+n-1,p);
p2 = i-get(0,0,n+n-1,i);
k += p2 - p1;
if (s[i]>0) k--;
vs[p] = vs[i] = true;
upd(0,0,n+n-1,p+1);
}
return 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... |