이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define meta int M = (L + R) / 2, x = 2 * id, y = x + 1
using namespace std;
queue<int> q[400001];
int res[400001];
int dp[400001];
struct Tree{
int tree[1600001];
void update(int id, int L, int R, int i){
if (L == R) {tree[id] = 1; return ;}
meta;
if (L <= i && i <= M) update(x, L, M, i);
else update(y, M + 1, R, i);
tree[id] = tree[x] + tree[y];
}
int query(int id, int l, int r, int L, int R) {
if (l <= L && R <= r) return tree[id];
if (l > R || L > r) return 0;
meta;
return query(x, l, r, L, M) + query(y, l, r, M + 1, R);
}
} T;
long long count_swaps(vector<int> v) {
int n = v.size(), num = n;
for (int i = n-1; i >= 0; i--) {
if (q[v[i] + n].empty()) {
if (v[i] > 0) {res[i+1] = num; q[n-v[i]].push(num-1);}
else {res[i+1] = num-1; q[n-v[i]].push(num);}
num -= 2;
}
else {res[i+1] = q[v[i]+n].front(); q[v[i]+n].pop();}
}
long long resp = 0;
for (int i = 1; i <= n; i++){
resp += T.query(1, res[i], n, 1, n);
T.update(1, 1, n, res[i]);
}
return resp;
}
# | 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... |