| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 483481 | Bogdan1110 | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ld long double
#define n_4 10010
#define n_5 100010
#define n_6 1000010
#define n_7 10000010
#define n_8 100000010
#define pii pair<int,int>
#define pll pair<long long,long long>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ld, null_type,less<ld>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key -> # less than k
// find_by_order -> k-th element
// pq max element
const int NMAX = 20010;
int seg[2*NMAX];
int lejzi[2*NMAX];
int nalaz[NMAX];
int mikimaus[NMAX];
void update(int l, int r, int nl, int nr, int node, int value) {
if ( l <= nl && r >= nr ) {
lejzi[node] += value;
return;
}
if ( r < nl || l > nr ) return;
update(l, r, (nl+nr)/2+1, nr, node*2+2, value);
update(l, r, nl, (nl+nr)/2, node*2+1, value);
}
int pronadji(int ind, int nl, int nr, int node) {
if ( nl == nr ) {
seg[node] += lejzi[node];
lejzi[node] = 0;
return seg[node];
}
seg[node] += lejzi[node];
lejzi[node*2+1] += lejzi[node];
lejzi[node*2+2] += lejzi[node];
lejzi[node] = 0;
if ( ind <= (nl + nr)/2 ) {
return pronadji(ind, nl, (nl + nr)/2, node*2+1);
}
else {
return pronadji(ind, (nl + nr)/2+1, nr, node*2+2);
}
}
ll count_swaps(int v[]) {
int N = abs(v[0]);
unordered_map<int,int>m;
for (int i = 0 ; i < N; i++ ) {
m[v[i]] = i;
if ( m.find(-v[i]) != m.end() ) {
nalaz[i] = m[-v[i]];
}
else nalaz[i] = -1;
}
for (int i = N-1; i >= 0 ; i-- ) {
if ( nalaz[i] != -1) {
mikimaus[nalaz[i]] = i;
}
}
ll rez = 0;
for (int i = 0 ; i < N; i++ ) {
//cout << mikimaus[i] << ' ';
if (mikimaus[i] ) {
int r = mikimaus[i] + pronadji(mikimaus[i],0,N-1,0);
int l = i + pronadji(i,0,N-1,0);
int cnt = r-l-1;
if ( v[i] > 0 ) cnt++;
l = i + 1;
r = mikimaus[i]-1;
if ( r >= l ) {
//cout << l << ' ' << r << ' ' ;
update(l,r,0,N-1,0,1);
}
//cout << cnt << endl ;
rez += cnt;
}
//for ( int j = 0 ; j < N ; j++ ) {
// cout << pronadji(j, 0, N-1, 0) << ' ';
//}cout << endl ;
}
return rez;
}