이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vv vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1;
struct seg{
int base;
vv<int> t;
void init(int n){
base = 1;
while(base < n) base <<= 1;
t.resize(base<<1, 0);
for(int i = 1; i <= n; ++i) t[i+base-1] = 1;
for(int i = base-1; i; --i) t[i] = t[i<<1]+t[i<<1|1];
}
void update(int i, int val){
for(i += base-1, t[i] = val, i >>= 1; i; i >>= 1) t[i] = t[i<<1]+t[i<<1|1];
}
int query_interval(int i, int s, int e, int x, int y){
if(x <= s && e <= y) return t[i];
int mid = (s+e)>>1, result = 0;
if(x <= mid) result += query_interval(i<<1, s, mid, x, y);
if(mid < y) result += query_interval(i<<1|1, mid+1, e, x, y);
return result;
}
int query(int l, int r){
if(l <= r) return query_interval(1, 1, base, max(1, l), min(base, r));
return 0;
}
};
ll count_swaps(vv<int> t){
int n = ssize(t);
set<int> s;
vv<set<int>> v(n+3);
for(int i = 0; i < n; ++i) t[i] = t[i] > 0 ? 2*t[i]+1 : -2*t[i], s.emplace(i), v[t[i]].emplace(i);
ll result = 0;
seg seg; seg.init(n+2);
for(int i = 0; i < n/2; ++i){
int posx = *s.begin(), x = t[posx];
int posy = *v[x^1].begin();
//~ printf("%d: %d %d: ", x, posx, posy);
if(x & 1) result += seg.query(posx+1, posy);
else result += seg.query(posx+2, posy);
seg.update(posx+1, 0), seg.update(posy+1, 0);
v[x].erase(posx), v[x^1].erase(posy);
s.erase(posx), s.erase(posy);
//~ printf("%lld\n", result);
}
return result;
}
#ifdef LOCAL
int main(){
int T = 1;
for(++T; --T; ){
int n; scanf("%d", &n);
vv<int> t(n<<1);
for(int i = 0; i < n<<1; ++i) scanf("%d", &t[i]);
ll result = count_swaps(t);
printf("%lld\n", result);
}
return 0;
}
#endif
# | 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... |