#include<iostream>
#include<cmath>
#include "shoes.h"
using namespace std;
#define int long long
typedef pair<int, int> pii;
struct FT
{
int N;
vector<int> v;
inline int query(int n)
{
int sum = 0;
for (n+=2; n; n-=n&-n)
sum += v[n];
return sum;
}
inline int ask(int a, int b)
{
return query(b) - query(a-1);
}
inline void upd(int n, int vv)
{
for (n+=2; n<N; n+=n&-n)
v[n] += vv;
}
FT(int cN): N(cN+5), v(N) { }
};
#undef int
long long count_swaps(std::vector<int> v)
#define int long long
{
int n = v.size();
vector<vector<pii>> sh(n+1);
for (int i=0;i<n;i++)
sh[abs(v[i])].push_back({i, v[i]>0});
int sum = 0;
FT ft(n);
for (int i=1;i<=n;i++)
{
vector<pii> &shi = sh[i];
int m = shi.size();
for (int sr=0, j=0;j<m;j++)
{
if (!shi[j].second) sum += sr, sr--;
else sr++;
}
for (int j=1;j<m;j+=2)
{
sum += ft.ask(shi[j-1].first, shi[j].first);
}
for (int j=0;j<m;j++)
ft.upd(shi[j].first, 1);
}
return sum;
}
#undef int
#ifdef lioraju
signed main()
{
int n; cin>>n, n*=2;
vector<int> v(n);
for (int &x: v)
cin>>x;
cout<<count_swaps(v)<<'\n';
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
256 KB |
Output is correct |
2 |
Correct |
5 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
256 KB |
Output is correct |
2 |
Correct |
5 ms |
256 KB |
Output is correct |
3 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
256 KB |
Output is correct |
2 |
Correct |
5 ms |
256 KB |
Output is correct |
3 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
256 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
256 KB |
Output is correct |
2 |
Correct |
5 ms |
256 KB |
Output is correct |
3 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
256 KB |
Output is correct |
2 |
Correct |
5 ms |
256 KB |
Output is correct |
3 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |