| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 822827 | vjudge1 | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "shoes.h"
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
using namespace std ;
const ull N = (1 << 18) ;
ull sum[2 * N + 1], psh[2 * N + 1] ;
void push(ull l, ull r, ull v)
{
if(!psh[v])
return ;
ull num = psh[v] ;
psh[v] &= 0 ;
sum[v] += num * (r - l + 1) ;
if(l == r)
return ;
psh[v * 2] += num ;
psh[v * 2 + 1] += num ;
}
void update(ull l, ull r, ull l1, ull r1, ull num, ull v)
{
push(l, r, v) ;
if(l > r1 || r < l1)
return ;
if(l1 <= l && r <= r1)
{
psh[v] = num ;
push(l, r, v) ;
return ;
}
ull mid = (l + r) >> 1 ;
update(l, mid, l1, r1, num, v * 2) ;
update(mid + 1, r, l1, r1, num, v * 2 + 1) ;
sum[v] = sum[v * 2] + sum[v * 2 + 1] ;
}
ull get_sum(ull l, ull r, ull ind, ull v)
{
push(l, r, v) ;
if(l > ind || r < ind)
return 0 ;
if(l == r)
return sum[v] ;
ull mid = (l + r) >> 1 ;
return get_sum(l, mid, ind, v * 2) + get_sum(mid + 1, r, ind, v * 2 + 1) ;
}
ull count_swaps(vector<int> v)
{
map<int, deque<int>> mp ;
ull ans = 0, n = v.size() ;
bool us[n + 1] = {} ;
for(ull i = 0 ; i < n ; i++)
mp[v[i]].push_back(i) ;
for(ull i = 0 ; i < n ; i++)
{
if(us[i])
continue ;
ull ind1 = i, ind2 = mp[-v[i]][0] ;
us[ind1] = 1 ;
us[ind2] = 1 ;
mp[v[i]].pop_front() ;
mp[-v[i]].pop_front() ;
update(0, N - 1, ind1 + 1, ind2 - 1, 1, 1) ;
ind1 += get_sum(0, N - 1, ind1, 1) ;
ind2 += get_sum(0, N - 1, ind2, 1) ;
if(v[i] > 0)
ans += ind2 - ind1 ;
else
ans += ind2 - ind1 - 1 ;
}
return ans ;
}
//signed main()
//{
// ios_base::sync_with_stdio( 0 ) ;
// cin.tie( 0 ) ;
// cout.tie( 0 ) ;
// ull n ;
// cin >> n ;
// vector<ull> v(n) ;
// for(ull i = 0 ; i < n ; i++)
// cin >> v[i] ;
// cout << count_swaps(v) ;
// return 0 ;
//}