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;
typedef long long ll;
const int Nmax = 1e5 + 5;
int n;
int F[Nmax], S[Nmax], a[Nmax], cnt[Nmax], sum_cnt[Nmax];
void norm()
{
int i;
for(i=1; i<=n; ++i)
if(a[i] > 0) ++sum_cnt[a[i]];
for(i=1; i<=n; ++i)
sum_cnt[i] += sum_cnt[i-1], cnt[i] = 0;
for(i=1; i<=n; ++i)
if(a[i] > 0)
{
++cnt[a[i]];
a[i] = sum_cnt[a[i] - 1] + cnt[a[i]];
S[a[i]] = i;
}
for(i=1; i<=n; ++i) cnt[i] = 0;
for(i=1; i<=n; ++i)
if(a[i] < 0)
{
a[i] *= -1;
++cnt[a[i]];
a[i] = sum_cnt[a[i] - 1] + cnt[a[i]];
F[a[i]] = i;
}
}
class AIB
{
int a[Nmax];
int ub(int x) { return (x&(-x)); }
public:
void clear()
{
memset(a, 0, sizeof(a));
}
int query(int x)
{
int ans = 0;
for(; x <= n; x += ub(x)) ans += a[x];
return ans;
}
void update(int x)
{
for(; x; x -= ub(x)) a[x] ++;
}
void update(int x, int y)
{
for(; x; x-=ub(x)) a[x] --;
for(; y; y-=ub(y)) a[y] ++;
}
} aib;
ll solve1()
{
ll ans = 0;
int i;
aib.clear();
for(i=1; i<=n; ++i)
if(i == max(F[a[i]], S[a[i]]))
{
int curr = min(F[a[i]], S[a[i]]);
ans += 2 * aib.query(curr);
aib.update(curr);
}
aib.clear();
for(i=1; i<=n; ++i)
if(i == max(F[a[i]], S[a[i]]))
{
int curr = min(F[a[i]], S[a[i]]);
ans += aib.query(curr);
aib.update(curr, i);
}
return ans;
}
ll solve2()
{
int i, ans = 0;
for(i=1; i<=n; ++i)
ans += (F[i] > S[i]);
return ans;
}
ll count_swaps(vector<int> s)
{
n = s.size();
int i;
for(i=1; i<=n; ++i) a[i] = s[i-1];
norm();
// for(i=1; i<=n; ++i) cerr << a[i] << ' '; cerr << "#\n";
// cerr << solve1() << '\n';
// cerr << solve2() << '\n';
return solve1() + solve2();
}
# | 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... |