제출 #792742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
792742		vjudge1	Bitaro's travel (JOI23_travel)	C++14	100 / 100	331 ms	22596 KiB

travel

#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 ;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 55 / 55