oj.uz

Submission #792750

# Submission time Handle Problem Language Result Execution time Memory
792750 2023-07-25T08:29:29 Z vjudge1 Lamps (JOI19_lamps) C++14
0 / 100
 1 ms 328 KB 
#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] ;
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] ;
    cin >> q ;
    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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 328 KB Output isn't correct
2 Halted 0 ms 0 KB -