oj.uz

Submission #796016

# Submission time Handle Problem Language Result Execution time Memory
796016 2023-07-28T04:16:53 Z 반딧불(#10068) Bitaro's travel (JOI23_travel) C++17
0 / 100
 396 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
    int tree[800002];

    void init(int i, int l, int r, int* v){
        if(l==r){
            tree[i] = v[l];
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, v);
        init(i*2+1, m+1, r, v);
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }

    int findRight(int i, int l, int r, int x, int lim){ /// lim �̻��� �� ã��
        if(r<x || tree[i] < lim) return r+1;
        if(l==r) return l;
        int m = (l+r)>>1;
        int tmp = findRight(i*2, l, m, x, lim);
        if(tmp == m+1) return findRight(i*2+1, m+1, r, x, lim);
        else return tmp;
    }

    int findLeft(int i, int l, int r, int x, int lim){
        if(x<l || tree[i] < lim) return l-1;
        if(l==r) return l;
        int m = (l+r)>>1;
        int tmp = findLeft(i*2+1, m+1, r, x, lim);
        if(tmp == m) return findLeft(i*2, l, m, x, lim);
        else return tmp;
    }
} tree;

int n, q;
int arr[200002];
int diff[200002];

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
    for(int i=1; i<n; i++) diff[i] = arr[i+1] - arr[i];
    tree.init(1, 1, n-1, diff);
    scanf("%d", &q);
    while(q--){
        int start;
        ll ans = 0;
        scanf("%d", &start);
        int idx = lower_bound(arr+1, arr+n+1, start) - arr;

        if(idx == n+1) ans = start - arr[n], start = n;
        else if(idx == 1) ans = arr[1] - start, start = 1;
        else if(arr[idx] - start >= start - arr[idx-1]) ans = start - arr[idx-1], start = idx-1;
        else ans = arr[idx] - start, start = idx;

        int s = start, e = start, x = start;
        while(1<s || e<n){
            if(s==1) ans += arr[n] - arr[x], e = n;
            else if(e==n) ans += arr[x] - arr[1], s = 1;
            else{
                if(arr[x] - arr[s-1] <= arr[e+1] - arr[x]) ans += arr[x] - arr[s-1], s--, x=s;
                else ans += arr[e+1] - arr[x], e++, x=e;
            }
        }

        printf("%lld\n", ans);
    }
}

Compilation message

travel.cpp: In function 'int main()':
travel.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
travel.cpp:46:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~
travel.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
travel.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d", &start);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Runtime error 396 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Runtime error 396 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Runtime error 344 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Runtime error 396 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -