oj.uz

Submission #1018664

# Submission time Handle Problem Language Result Execution time Memory
1018664 2024-07-10T08:06:38 Z NintsiChkhaidze Bitaro's travel (JOI23_travel) C++17
5 / 100
 352 ms 11464 KB 
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define ll long long
#define left h*2,l,(l + r)/2
#define right h*2+1,(l + r)/2 + 1,r
using namespace std;

const int N = 2e5 + 5,mod = 1e9 + 7;
int a[N],t[5][4*N];

void build(int h,int l,int r){
  if (l == r){
    t[1][h] = 2*a[l] - a[l + 1];
    t[0][h] = 2*a[l] - a[l - 1];
    return;
  }

  build(left);
  build(right);
  t[1][h] = min(t[1][h*2],t[1][h*2+1]); 
  t[0][h] = max(t[0][h*2],t[0][h*2+1]); 
}

int getr(int h,int l,int r,int L,int R,int v){
  if (r < L || R < l) return -1;
  if (L <= l && r <= R) {
    if (t[1][h] > v) return -1;
    if (l == r) return l;
    if (t[1][h*2] <= v) return getr(left,L,R,v);
    return getr(right,L,R,v);
  }
  int y = getr(right,L,R,v);
  if (y != -1) return y;
  return getr(left,L,R,v);
}

int getl(int h,int l,int r,int L,int R,int v){
  if (r < L || R < l) return -1;
  if (L <= l && r <= R) {
    if (t[0][h] <= v) return -1;
    if (l == r) return l;
    if (t[0][h*2+1] > v) return getl(right,L,R,v);
    return getl(left,L,R,v);
  }
  int y = getl(left,L,R,v);
  if (y != -1) return y;
  return getl(right,L,R,v);
}


int main() {
  ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

  int n;
  cin>>n;

  for (int i = 1; i <= n; i++){
    cin >> a[i];
  }

  build(1,1,n);

  int q;
  cin>>q;

  while (q--){

    int s;
    cin>>s;

    int le = 1,ri = n,R = n + 1;
    while (le <= ri){
      int mid = (le + ri) >> 1;
      if (a[mid] > s) {
        R = mid;
        ri = mid - 1;
      }else{
        le = mid + 1;
      }
    }

    le = 1; ri = n; int L = 0;
    while (le <= ri){
      int mid = (le + ri) >> 1;
      if (a[mid] < s){
        L = mid;
        le = mid + 1;
      }else{
        ri = mid - 1;
      }
    }

    int ans=0;
    if (L == 0){
      ans += (a[n] - s);
      cout<<ans<<endl;
      continue;
    }else if (R == n + 1){
      ans += (s - a[1]);
      cout<<ans<<endl;
      continue;
    }

    int dir = 1;
    //dir == 1 -> right
    //dir == 0 <- left

    if (a[R] - s < s - a[L]){
      dir = 1;
      ans += (a[R] - s);
      s = a[R];
    }else{
      dir = 0;
      ans += (s - a[L]);
      s = a[L];
    }

    while (L != 0 && R != n + 1){
      if (dir == 1){
        // vedzebt R -ze meti an tol umcires r-s romlistvisac
        //2*x[r] - x[r + 1] <= x[L]
        int r = getr(1,1,n,R,n,a[L]);
        if (r == -1) r = n;

        ans += a[r] - s;
        ans += a[r] - a[L];
        s = a[L];
        R = r + 1;
      }else{
        //vedzebt L-ze naklebi an tol udides l-s romlistvisac
        //2*x[l] - x[l - 1] > x[R] 

        int l = getl(1,1,n,1,L,a[R]);
        if (l == -1) l = 1;

        ans += s - a[l];
        ans += a[R] - a[l];
        s = a[R];
        L = l - 1;
      }

      dir ^= 1;
    }

    if (L == 0){
      ans += (a[n] - s);
    }else if (R == n + 1){
      ans += (s - a[1]);
    }

    cout<<ans<<endl;
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Incorrect 15 ms 6252 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 294 ms 9416 KB Output is correct
8 Correct 287 ms 11464 KB Output is correct
9 Correct 306 ms 11348 KB Output is correct
10 Correct 293 ms 10080 KB Output is correct
11 Correct 352 ms 10084 KB Output is correct
12 Correct 302 ms 10324 KB Output is correct
13 Correct 224 ms 6228 KB Output is correct
14 Correct 233 ms 3676 KB Output is correct
15 Incorrect 288 ms 11344 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Incorrect 15 ms 6252 KB Output isn't correct
18 Halted 0 ms 0 KB -