oj.uz

답안 #1078295

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1078295 2024-08-27T14:59:09 Z GrindMachine Bitaro's travel (JOI23_travel) C++17
100 / 100
 279 ms 86352 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*

read the solution a long time ago, remember the key ideas

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct sparse_table {
    /*============================*/

    T merge(T a, T b) {
        return max(a,b);
    }

    /*============================*/

    vector<vector<T>> table;
    vector<int> bin_log;
    int LOG = 0;

    sparse_table() {

    }

    sparse_table(vector<T> &a, int n) {
        while ((1 << LOG) <= n) LOG++;

        table = vector<vector<T>>(n, vector<T>(LOG));
        bin_log = vector<int>(n + 1);

        rep(i, n) table[i][0] = a[i];

        rep1(j, LOG - 1) {
            rep(i, n) {
                int jump = 1 << (j - 1);
                if (i + jump >= n) {
                    break;
                }

                table[i][j] = merge(table[i][j - 1], table[i + jump][j - 1]);
            }
        }

        bin_log[1] = 0;
        for (int i = 2; i <= n; ++i) {
            bin_log[i] = bin_log[i / 2] + 1;
        }
    }

    T query(int l, int r) {
        int len = r - l + 1;
        int k = bin_log[len];

        T val1 = table[l][k];
        T val2 = table[r - (1 << k) + 1][k];

        return merge(val1, val2);
    }
};

void solve(int test_case)
{
    ll n; cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    
    vector<ll> val1(n);
    rep(i,n-1) val1[i] = 2*a[i+1]-a[i];

    vector<ll> val2(n);
    rep1(i,n-1) val2[i] = a[i]-2*a[i-1];

    sparse_table<ll> st1(val1,n), st2(val2,n);

    vector<ll> b(n);
    rep(i,n){
        ll l = i, r = i, pos = i;
        ll cost = 0;

        while(!(l == 0 and r == n-1)){
            ll left_cost = inf2, right_cost = inf2;
            if(l-1 >= 0){
                left_cost = a[pos]-a[l-1];
            }
            if(r+1 < n){
                right_cost = a[r+1]-a[pos];
            }

            if(left_cost <= right_cost){
                cost += left_cost;
                ll lo = 0, hi = l-2;
                ll best = l-1;
                ll x = inf2;
                if(r+1 < n) x = a[r+1];

                while(lo <= hi){
                    ll mid = (lo+hi) >> 1;
                    if(st1.query(mid,l-2) <= x){
                        best = mid;
                        hi = mid-1;
                    }
                    else{
                        lo = mid+1;
                    }
                }

                cost += a[l-1]-a[best];
                pos = best;
                l = best;
            }
            else{
                cost += right_cost;
                ll lo = r+2, hi = n-1;
                ll best = r+1;
                ll x = -inf2;
                if(l-1 >= 0) x = a[l-1];

                while(lo <= hi){
                    ll mid = (lo+hi) >> 1;
                    if(st2.query(r+2,mid) < -x){
                        best = mid;
                        lo = mid+1;
                    }
                    else{
                        hi = mid-1;
                    }
                }

                cost += a[best]-a[r+1];
                pos = best;
                r = pos;
            }
        }

        b[i] = cost;
    }

    ll q; cin >> q;
    while(q--){
        ll x; cin >> x;
        ll p = lower_bound(all(a),x)-a.begin();
        ll right_cost = inf2, left_cost = inf2;
        if(p < n){
            right_cost = abs(a[p]-x);
        }
        if(p-1 >= 0){
            left_cost = abs(a[p-1]-x);
        }

        ll ans = min(left_cost,right_cost);

        if(left_cost <= right_cost){
            ans += b[p-1];
        }
        else{
            ans += b[p];
        }

        cout << ans << endl;
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 984 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 1 ms 856 KB Output is correct
16 Correct 1 ms 860 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 984 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 1 ms 856 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Correct 199 ms 80088 KB Output is correct
18 Correct 198 ms 82144 KB Output is correct
19 Correct 197 ms 82000 KB Output is correct
20 Correct 205 ms 81984 KB Output is correct
21 Correct 191 ms 82120 KB Output is correct
22 Correct 210 ms 82164 KB Output is correct
23 Correct 190 ms 82000 KB Output is correct
24 Correct 151 ms 82020 KB Output is correct
25 Correct 159 ms 82200 KB Output is correct
26 Correct 150 ms 82000 KB Output is correct
27 Correct 156 ms 82128 KB Output is correct
28 Correct 160 ms 82004 KB Output is correct
29 Correct 228 ms 82136 KB Output is correct
30 Correct 225 ms 82188 KB Output is correct
31 Correct 238 ms 82256 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 201 ms 83140 KB Output is correct
8 Correct 165 ms 83232 KB Output is correct
9 Correct 166 ms 83028 KB Output is correct
10 Correct 170 ms 83152 KB Output is correct
11 Correct 171 ms 83348 KB Output is correct
12 Correct 200 ms 83124 KB Output is correct
13 Correct 28 ms 3464 KB Output is correct
14 Correct 18 ms 1368 KB Output is correct
15 Correct 178 ms 84516 KB Output is correct
16 Correct 237 ms 85152 KB Output is correct
17 Correct 197 ms 85072 KB Output is correct
18 Correct 28 ms 4176 KB Output is correct

Subtask #4
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 984 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 1 ms 856 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Correct 199 ms 80088 KB Output is correct
18 Correct 198 ms 82144 KB Output is correct
19 Correct 197 ms 82000 KB Output is correct
20 Correct 205 ms 81984 KB Output is correct
21 Correct 191 ms 82120 KB Output is correct
22 Correct 210 ms 82164 KB Output is correct
23 Correct 190 ms 82000 KB Output is correct
24 Correct 151 ms 82020 KB Output is correct
25 Correct 159 ms 82200 KB Output is correct
26 Correct 150 ms 82000 KB Output is correct
27 Correct 156 ms 82128 KB Output is correct
28 Correct 160 ms 82004 KB Output is correct
29 Correct 228 ms 82136 KB Output is correct
30 Correct 225 ms 82188 KB Output is correct
31 Correct 238 ms 82256 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 344 KB Output is correct
38 Correct 201 ms 83140 KB Output is correct
39 Correct 165 ms 83232 KB Output is correct
40 Correct 166 ms 83028 KB Output is correct
41 Correct 170 ms 83152 KB Output is correct
42 Correct 171 ms 83348 KB Output is correct
43 Correct 200 ms 83124 KB Output is correct
44 Correct 28 ms 3464 KB Output is correct
45 Correct 18 ms 1368 KB Output is correct
46 Correct 178 ms 84516 KB Output is correct
47 Correct 237 ms 85152 KB Output is correct
48 Correct 197 ms 85072 KB Output is correct
49 Correct 28 ms 4176 KB Output is correct
50 Correct 243 ms 86352 KB Output is correct
51 Correct 233 ms 86208 KB Output is correct
52 Correct 237 ms 86216 KB Output is correct
53 Correct 224 ms 86308 KB Output is correct
54 Correct 222 ms 86244 KB Output is correct
55 Correct 220 ms 86352 KB Output is correct
56 Correct 268 ms 86096 KB Output is correct
57 Correct 255 ms 86100 KB Output is correct
58 Correct 279 ms 86092 KB Output is correct