이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;
void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 2e5 + 10;
int n, f[maxn];
vector<int> idx[maxn][2];
bool mark[maxn];
void add(int idx, int x){
for (; idx <= n; idx += idx & -idx) f[idx] += x;
}
int get(int idx){
int res = 0;
for (; idx; idx -= idx & -idx) res += f[idx];
return res;
}
ll count_swaps(vector<int> s) {
n = s.size();
for (int i = 0; i < n; i++){
add(i+1, 1);
if (s[i] < 0) idx[-s[i]][0].push_back(i);
else idx[s[i]][1].push_back(i);
mark[i] = true;
}
for (int i = 1; i <= n; i++){
reverse(all(idx[i][0]));
reverse(all(idx[i][1]));
}
ll ans = 0;
for (int i = 0; i < n; i++){
if (!mark[i]) continue;
mark[i] = false;
if (s[i] > 0) ans++;
int ptr = abs(s[i]);
int ptr2 = (s[i] > 0? 1: 0);
add(i+1, -1);
idx[ptr][ptr2].pop_back();
ans += get(idx[ptr][1-ptr2].back());
add(idx[ptr][1-ptr2].back()+1, -1);
mark[idx[ptr][1-ptr2].back()] = false;
idx[ptr][1-ptr2].pop_back();
}
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... |