이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "shoes.h"
#define ff first
#define ss second
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> ii;
const int N = 1e5 + 10;
int n,a[N<<1],cn = 0;
vi s;
deque<ii> d[N];
struct Fenwick_Tree{
int n,p[N<<1];
void up(int ps,int dl){
for(; ps <= n; ps = (ps|(ps-1))+1)
p[ps] += dl;
}
int get(int ps){
int ans = 0;
for(; ps >= 1; ps = (ps&(ps-1)))
ans += p[ps];
return ans;
}
int ran(int l,int r){
if(l > r) return 0;
return get(r)-get(l-1);
}
} st;
ll count_swaps(vi S){
s = S;
n = ((int) s.size())>>1;
for(int i = 0; i < (n<<1); ++i){
int id = abs(s[i]), sg = (s[i] < 0 ? 0 : 1);
if(d[id].empty() or d[id].back().ss == sg){
d[id].push_back({i,sg});
if(sg == 0)
a[i] = cn<<1;
else
a[i] = (cn<<1)|1;
cn++;
continue;
}
ii tr = d[id].back();
if(tr.ss == 0)
a[i] = a[tr.ff]+1;
else
a[i] = a[tr.ff]-1;
d[id].pop_back();
}
ll ans = 0;
st.n = (n<<1);
for(int i = 0; i < (n<<1); ++i){
st.up(a[i]+1,1);
ans += ((ll) st.ran(a[i]+2,n<<1));
}
return ans;
}
// int main(){
// cout << count_swaps({2,1,-1,-2}) << endl;
// return 0;
// }
# | 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... |