#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else
#define dbg(...) 199958
#endif
#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
if(x>y){
x=y;
return true;
}
return false;
}
template<class T, class F>
bool chmax(T &x, F y){
if(x<y){
x=y;
return true;
}
return false;
}
double pass_time=0;
#include<vector>
template <class T = long long >
struct BIT {
int n;
std::vector<T>data;
void add(int i,T x){
assert(i>=0&&i<n);
i++;
for(;i<=n;){
data[i - 1] += x;
i += (i & -i);
}
return;
}
T internal_sum(int r){
T ret = 0;
for(;r;){
ret += data[r - 1];
r -= (r & -r);
}
return ret;
}
T sum(int l,int r){
return internal_sum(r)-internal_sum(l);
}
BIT():n(0), data(0) {}
BIT(int N):n(N), data(N) {}
BIT(std::vector<T>& a){
n = a.size();
data.assign(n, 0);
for (int i = 0; i < n; i++)add(i, a[i]);
}
int lower_bound(T w) {
if (w <= 0) {
return 0;
} else {
int x = 0, r = 1;
while (r < n) r = r << 1;
for (int len = r; len > 0; len = len >> 1) {
if (x + len < n && data[x + len] < w) {
w -= data[x + len];
x += len;
}
}
return x;
}
}
};
#include"shoes.h"
long long count_swaps(vector<int>S){
int n=S.size();
map<int,vc<int>>vs;
rep(i,n){
vs[S[i]].push_back(i);
}
set<pair<int,int>>st;
for(auto&[x,y]:vs){
if(x<0)continue;
rep(j,y.size()){
int i1=y[j],i2=vs[-x][j];
st.insert(minmax(i1,i2));
}
}
BIT<int>bit(n);
rep(i,n){
bit.add(i,1);
}
ll ans=0;
for(auto&[x,y]:st){
bit.add(x,-1);
bit.add(y,-1);
ans+=bit.sum(0,x);
ans+=bit.sum(0,y);
if(S[x]>0)++ans;
}
return ans;
}
# | 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... |