| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 825763 | vjudge1 | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
const long long N = (1 << 18);
long long t[2 * N + 100], sum[2 * N + 100], p = 0;
vector <long long> S;
void build (long long x, long long tl, long long tr){
if (tl == tr){
t[x] = tl;
}
else{
long long mid = (tl + tr)/2;
build(x * 2, tl, mid);
build(x * 2 + 1, mid + 1, tr);
t[x] = t[2 * x] + t[2 * x + 1];
}
}
void update(long long l, long long r, long long x, long long tl, long long tr){
if (l > r){
return ;
}
else if (l == tl && r == tr){
sum[x]++;
}
else{
//cout << l << " " << r << " " << x << " " << tl << " " << tr << "\n";
long long tmid = (tl + tr)/2;
update(l, min(tmid, r), x * 2, tl, tmid);
update(max(l, tmid + 1), r, x * 2 + 1, tmid + 1, tr);
}
}
long long get(long long num, long long x, long long tl, long long tr){
if (tl == tr){
p+=sum[x];
return t[x] + sum[x];
}
else{
p+=sum[x];
long long tmid = (tl + tr)/2;
if (num > tmid)
return get(num, x * 2 + 1, tmid + 1, tr) + sum[x];
else
return get(num, x * 2, tl, tmid) + sum[x];
}
}
long long count_swaps(vector<long long> s) {
long long ans = 0, n = s.size();
map <long long, deque <long long>> mp;
long long used[n];
build(1, 0, n - 1);
for (long long i = 0 ; i < n ; i++){
used[i] = 0;
//cout << get(i, 1, 0, n - 1) << "\n";
mp[s[i]].push_back(i);
}
for (long long i = 0 ; i < n ; i++){
if (used[i])
continue ;
long long cur1 = i, cur2 = mp[s[i] * -1][0];
mp[s[i] * -1].pop_front();
mp[s[i]].pop_front();
//cout << get(cur1, 1, 0, n - 1) << " " << get(cur2, 1, 0, n - 1) << "\n";
ans+=max(get(cur1, 1, 0, n - 1), get(cur2, 1, 0, n - 1)) - min(get(cur1, 1, 0, n - 1), get(cur2, 1, 0, n - 1)) - 1;
update(min(cur1, cur2), max(cur1, cur2), 1, 0, n - 1);
//cout << get(cur1, 1, 0, n - 1) << " " << get(cur2, 1, 0, n - 1) << "\n";
used[cur1] = 1;
used[cur2] = 1;
if (s[i] > 0)
ans++;
}
return ans;
}