| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 228317 | chctxdy68 | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pci pair <char, int>
#define pld pair <ld, ld>
#define ppld pair <pld, pld>
#define ppll pair <pll, pll>
#define pldl pair <ld, ll>
#define vll vector <ll>
#define vvll vector <vll>
#define vpll vector <pll>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define mll map <ll, ll>
#define fastmap gp_hash_table
#define cd complex <double>
#define vcd vector <cd>
#define PI 3.14159265358979
#define ordered_set tree <ll, null_type, less <ll>, rb_tree_tag, tree_order_statistics_node_update>
#pragma 03
#include "shoes.h"
using namespace std;
using namespace __gnu_pbds;
queue <ll> rs[100005], ls[100005];
ll st[800005];
bool marked[200005];
void update(ll root, ll l, ll r, ll i, ll val){
if (i < l || i > r) return;
if (l == r){
st[root] = val; return;
}
ll mid = (l + r) / 2;
update(root * 2 + 1, l, mid, i, val);
update(root * 2 + 2, mid + 1, r, i, val);
st[root] = st[root * 2 + 1] + st[root * 2 + 2];
}
ll query(ll root, ll l, ll r, ll x, ll y){
if (y < l || x > r) return 0;
if (x <= l && y >= r) return st[root];
ll mid = (l + r) / 2;
return query(root * 2 + 1, l, mid, x, y) + query(root * 2 + 2, mid + 1, r, x, y);
}
ll count_swaps(vll a){
for (ll i = 0; i < a.size(); i++){
if (a[i] < 0) ls[-a[i]].push(i);
else rs[a[i]].push(a[i]);
}
ll ans = 0;
ll n = a.size();
for (ll i = 0; i < a.size(); i++) update(0, 0, n - 1, i, 1);
for (ll i = 0; i < a.size(); i++){
if (marked[i]) continue;
marked[i] = 1;
if (a[i] < 0){
ll p = rs[-a[i]].front(); rs[-a[i]].pop();
if (i + 1 <= p - 1) ans += query(0, 0, n - 1, i + 1, p - 1);
update(0, 0, n - 1, i, 0); update(0, 0, n - 1, p, 0);
marked[p] = 1;
}
else{
ll p = ls[a[i]].front(); ls[a[i]].pop();
if (i + 1 <= p - 1) ans += (query(0, 0, n - 1, i + 1, p - 1));
ans++;
update(0, 0, n - 1, i, 0); update(0, 0, n - 1, p, 0);
marked[p] = 1;
}
}
return ans;
}