| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 239623 | ant101 | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
#include <shoes.h>
using namespace std;
//#define RDEBUG 1
#ifdef RDEBUG
#define D(x) x
#else
#define D(x)
#endif
#define inf 0x7fffffff
#define MOD 1000000007
typedef long long ll;
ll add(ll a, ll b) {
a += b;
if(a >= MOD) {
a -= MOD;
}
return a;
}
ll sub(ll a, ll b) {
a -= b;
if(a < 0) {
a += MOD;
}
return a;
}
ll mul(ll a, ll b) {
return (a * b)%MOD;
}
void add_self(ll& a, ll b) {
a = add(a, b);
}
void sub_self(ll& a, ll b) {
a = sub(a, b);
}
void mul_self(ll& a, ll b) {
a = mul(a, b);
}
const ll MAXN = 200010;
ll tree[MAXN];
ll N;
void update(ll ind, ll num) {
while (ind<=MAXN) {
tree[ind]+=num;
ind+=(ind&-ind);
}
}
ll getsum(ll ind) {
ll sum = 0;
while (ind) {
sum+=tree[ind];
ind-=(ind&-ind);
}
return sum;
}
map<ll, queue<ll>> closest;
ll closestind[MAXN];
ll vis[MAXN];
ll S[MAXN];
long long count_swaps(std::vector<int> s) {
N = s.size();
for (ll i = 0; i<s.size(); i++) S[i+1] = s[i];
for (ll i = N; i>=1; i--) {
if (closest.find(-S[i]) != closest.end()) {
closestind[i] = closest[-S[i]].front();
closest[-S[i]].pop();
}
if (closest.find(S[i]) == closest.end()) {
queue<ll> q1;
closest[S[i]] = q1;
}
closest[S[i]].push(i);
}
ll ans = 0;
for (ll i = 1; i<=N; i++) {
if (!vis[i]) {
ans+=closestind[i]-i-1-(getsum(closestind[i])-getsum(i))+(S[i] > 0);
update(closestind[i], 1);
vis[closestind[i]] = 1;
}
}
return ans;
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
// cin >> N;
// for (ll i = 1; i<=N; i++) cin >> S[i];
// for (ll i = N; i>=1; i--) {
// if (closest.find(-S[i]) != closest.end()) {
// closestind[i] = closest[-S[i]];
// }
// closest[S[i]] = i;
// }
// ll ans = 0;
// for (ll i = 1; i<=N; i++) {
// if (!vis[i]) {
// ans+=closestind[i]-i-1-(getsum(closestind[i])-getsum(i))+(S[i] > 0);
// update(closestind[i], 1);
// vis[closestind[i]] = 1;
// }
// }
// cout << ans << "\n";
return 0;
}