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 <bits/stdc++.h>
#include "shoes.h"
using namespace std;
struct segtree{
vector<int> val;
vector<int> left, right;
int n;
segtree(int _n){
n=1;
while(n<_n) n*=2;
val.resize(n);
left.resize(n);
right.resize(n);
for(int i=0; i<n; i++){
left[n+i]=right[n+i]=i;
}
for(int i=n-1; i>0; i--){
left[i]=left[2*i];
right[i]=right[2*i+1];
}
}
void set(int ind, int vl){
ind+=n;
val[ind]=vl;
ind/=2;
while(ind>0){
val[ind]=val[ind*2]+val[ind*2+1];
}
}
int query(int l, int r, int x=1){
if(l>r) return 0;
if(l>right[x] || r<left[x]) return 0;
if(l<=left[x] && right[x]<=r) return val[x];
return query(l,r,2*x)+query(l,r,2*x+1);
}
};
long long count_swaps(std::vector<int> s) {
map<int,queue<int>> m;
vector<int> arr;
int ctr=0;
for(auto i:s){
if(m[i].size()>0){
arr.push_back(m[i].front());
m[i].pop();
}
else{
arr.push_back(2*ctr+i<0);
m[-i].push(2*ctr+(-i<0));
}
}
segtree tree(s.size());
long long res=0;
for(auto i:arr){
tree.set(i, 1);
res+=tree.query(0, i-1);
}
return res;
}
# | 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... |