이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define si second
#define ar array
#define pb push_back
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;
typedef vector<int> vi;
template<typename T> bool chmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int N = 100010;
int ans;
int done[N];
vector<int> occ[N][2]; //0-negative,1-positive
int fw[N], fw2[N];
void update(int x, int y, int v) {
++x, ++y;
for (int tx=x; tx < N; tx += tx&(-tx)) fw[tx] += v, fw2[tx] -= v*(x-1);
for (int ty=y+1; ty < N; ty += ty&(-ty)) fw[ty] -= v, fw2[ty] += v*y;
}
int sum (int x) {
++x;
int res = 0;
for (int tx=x; tx; tx -= tx&(-tx)) res += fw[tx]*x + fw2[tx];
return res;
}
int query(int x, int y) {
++x, ++y;
return sum(y)-sum(x-1);
}
long long count_swaps(std::vector<int> s) {
int n = s.size();
for (int i = n-1; i >= 0; --i) {
occ[abs(s[i])][s[i] > 0].pb(i);
update(i, i, i);
}
for (int i = 0; i < n; ++i) {
if (done[i]) continue;
bool flag = s[i] > 0;
int nex = occ[abs(s[i])][!flag].back();
occ[abs(s[i])][!flag].pop_back();
ans += query(nex, nex) - query(i, i) + (query(i, i) % 2 != flag);
update(i + 1, nex - 1, 1);
done[nex] = 1;
}
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... |