이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std ;
const ll N = 2e5 ;
ll n, q, x[N + 2], abu[N + 2] ;
bool flag ;
signed main()
{
ios_base::sync_with_stdio( 0 ) ;
cin.tie( 0 ) ;
cout.tie( 0 ) ;
cin >> n ;
x[0] = -1e18 ;
x[n + 1] = 1e18 ;
for(ll i = 1 ; i <= n ; i++)
cin >> x[i] ;
for(ll i = 1 ; i < n ; i++)
if(x[i + 1] - x[i] > 100)
flag = 1 ;
cin >> q ;
if(q == 1)
{
ll ans = 0, pos ;
cin >> pos ;
set<ll> s_neg, s_pos ;
for(ll i = 1 ; i <= n ; i++)
s_pos.insert(x[i]), s_neg.insert(-x[i]) ;
while(s_pos.size())
{
ll l = -1e18, r = 1e18 ;
if(s_pos.lower_bound(pos) != s_pos.end())
r = *s_pos.lower_bound(pos) ;
if(s_neg.lower_bound(-pos) != s_neg.end())
l = -(*s_neg.lower_bound(-pos)) ;
if(pos - l <= r - pos)
{
ans += pos - l ;
pos = l ;
s_neg.erase(-l) ;
s_pos.erase(l) ;
}
else
{
ans += r - pos ;
pos = r ;
s_neg.erase(-r) ;
s_pos.erase(r) ;
}
}
cout << ans ;
return 0 ;
}
// if(!flag)
// {
// for(ll i = 1 ; i <= n ; i++)
// {
// ll l = i - 1, r = i + 1, now = i ;
// while(x[now] - x[l] <= 100ll && x[r] - x[now] <= 100ll)
// if(x[now] - x[l] <= x[r] - x[now])
// {
// abu[i] += x[now] - x[l] ;
// now = l ;
// l-- ;
// }
// else
// {
// abu[i] += x[r] - x[now] ;
// now = r ;
// r++ ;
// }
// if(l && r <= n)
// {
// if(x[now] - x[l] <= 100)
// abu[i] += x[now] - x[1] ;
// else
// abu[i] += x[n] - x[now] ;
// }
// abu[i] += x[n] - x[1] ;
// }
// while(q--)
// {
// ll pos, l = 0, r = n + 1 ;
// cin >> pos ;
// while(l + 1 < r)
// {
// ll mid = (l + r) >> 1 ;
// if(x[mid] <= pos)l = mid ;
// else r = mid ;
// }
// if(pos - x[l] <= x[r] - pos)
// cout << abu[l] + pos - x[l] ;
// else
// cout << abu[r] + x[r] - pos ;
// cout << '\n' ;
// }
// }
// else
// {
for(ll i = 1 ; i <= n ; i++)
{
ll l = i - 1, r = i + 1, now = i ;
while(l && r <= n)
if(x[now] - x[l] <= x[r] - x[now])
{
ll l1 = 0, r1 = l ;
while(l1 + 1 < r1)
{
ll mid = (l1 + r1) >> 1 ;
if(x[now] - x[mid] <= x[r] - x[now])r1 = mid ;
else l1 = mid ;
}
abu[i] += x[now] - x[r1] ;
now = r1 ;
l = r1 - 1 ;
}
else
{
ll l1 = r, r1 = n + 1 ;
while(l1 + 1 < r1)
{
ll mid = (l1 + r1) >> 1 ;
if(x[now] - x[l] > x[mid] - x[now])l1 = mid ;
else r1 = mid ;
}
abu[i] += x[l1] - x[now] ;
now = l1 ;
r = l1 + 1 ;
}
abu[i] += x[n] - x[1] ;
}
while(q--)
{
ll pos, l = 0, r = n + 1 ;
cin >> pos ;
while(l + 1 < r)
{
ll mid = (l + r) >> 1 ;
if(x[mid] <= pos)l = mid ;
else r = mid ;
}
if(pos - x[l] <= x[r] - pos)
cout << abu[l] + pos - x[l] ;
else
cout << abu[r] + x[r] - pos ;
cout << '\n' ;
}
// }
return 0 ;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |