Submission #1187204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187204		avighna	Bitaro, who Leaps through Time (JOI19_timeleap)	C11	0 / 100	1542 ms	358008 KiB

timeleap

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define N 300001
#define LIM 19
#define INF 1000000000000000LL

typedef long long ll;

typedef struct {
  ll a, b, c, d;
  int i;
} Query;

typedef struct {
  ll cost, time;
} Pair;

ll l[N], r[N], t[N], ans[N], jump_min[N][LIM], jump_max[N][LIM], free_cit[N][3];
Pair ansl[N][LIM], ansr[N][LIM], ansm[N][LIM];

int n, q;

Pair trans(int i, int bt, int time) {
  if (time <= l[i]) {
    return ansl[i][bt];
  }
  return ansm[i][bt];
}

void binary_search(int i, int t, int *idx1, int *idx2) {
  *idx1 = *idx2 = i;
  ll max_val = l[i] - i, min_val = r[i] - i - 1;
  for (int bt = LIM - 1; bt >= 0; --bt) {
    if (*idx1 + (1 << bt) < n) {
      ll m1 = max_val;
      if (jump_max[*idx1 + 1][bt] > m1)
        m1 = jump_max[*idx1 + 1][bt];
      if (m1 <= t - i) {
        max_val = m1;
        *idx1 += 1 << bt;
      }
    }
    if (*idx2 + (1 << bt) < n) {
      ll m2 = min_val;
      if (jump_min[*idx2 + 1][bt] < m2)
        m2 = jump_min[*idx2 + 1][bt];
      if (t - i <= m2) {
        min_val = m2;
        *idx2 += 1 << bt;
      }
    }
  }
  if (max_val <= t - i)
    *idx1 = *idx1 + 1 < n ? *idx1 + 1 : n;
  if (t - i <= min_val)
    *idx2 = *idx2 + 1 < n ? *idx2 + 1 : n;
}

Pair __ans(int i, int x, ll t) {
  ll ans = 0;
  for (int bt = 0; bt < LIM; ++bt) {
    if (x & (1 << bt)) {
      Pair next;
      if (t <= l[i]) {
        next = ansl[i][bt];
      } else if (t >= r[i] - 1) {
        next = ansr[i][bt];
        ans += t - r[i] + 1;
      } else {
        next = ansm[i][bt];
      }
      ans += next.cost;
      t = next.time;
      i += (1 << bt);
    }
  }
  return (Pair){ans, t};
}

Pair _ans(int i, int x, ll t) {
  int idx1, idx2;
  binary_search(i, t, &idx1, &idx2);
  ll free_jumps = (idx1 < idx2 ? idx1 : idx2) - i;
  if (x <= free_jumps) {
    ll del = t + x > r[i + x] - 1 ? t + x - (r[i + x] - 1) : 0;
    Pair res = {del, t + x - del};
    return res;
  }
  if (idx1 < idx2) {
    return __ans(idx1, x - free_jumps, l[idx1]);
  } else {
    Pair p = __ans(idx2, x - free_jumps, r[idx2] - 1);
    assert((t + free_jumps) - (r[idx2] - 1) > 0);
    Pair res = {t + free_jumps - r[idx2] + p.cost + 1, p.time};
    return res;
  }
}

ll adjust(int i, int t) { return t - r[i + 1] + 2 > 0 ? t - r[i + 1] + 2 : 0; }

void solve(Query *queries, int qsize) {
  for (int i = 0, time = l[0]; i < n; ++i) {
    if (time < l[i]) {
      time = l[i];
    } else if (time > r[i] - 1) {
      time = r[i] - 1;
    }
    t[i] = time;
    time++;
  }
  for (int i = 0; i < n; ++i) {
    ll v1 = adjust(i, l[i]);
    ll v2 = adjust(i, r[i] - 1);
    ll v3 = adjust(i, t[i]);
    ansl[i][0] = (Pair){v1, l[i] - v1 + 1};
    ansr[i][0] = (Pair){v2, r[i] - v2};
    ansm[i][0] = (Pair){v3, t[i] - v3 + 1};
    jump_max[i][0] = l[i] - i;
    jump_min[i][0] = r[i] - i - 1;
  }
  for (int bt = 1; bt < LIM; ++bt) {
    for (int i = 0; i < n; ++i) {
      jump_min[i][bt] = jump_min[i][bt - 1];
      jump_max[i][bt] = jump_max[i][bt - 1];
      if (i + (1 << (bt - 1)) < n) {
        if (jump_min[i + (1 << (bt - 1))][bt - 1] < jump_min[i][bt])
          jump_min[i][bt] = jump_min[i + (1 << (bt - 1))][bt - 1];
        if (jump_max[i + (1 << (bt - 1))][bt - 1] > jump_max[i][bt])
          jump_max[i][bt] = jump_max[i + (1 << (bt - 1))][bt - 1];
      }
    }
  }
  for (int i = 0, idx1, idx2; i < n; ++i) {
    binary_search(i, l[i], &idx1, &idx2);
    free_cit[i][0] = (idx1 < idx2 ? idx1 : idx2) - i;
    binary_search(i, r[i] - 1, &idx1, &idx2);
    free_cit[i][1] = (idx1 < idx2 ? idx1 : idx2) - i;
    binary_search(i, t[i], &idx1, &idx2);
    free_cit[i][2] = (idx1 < idx2 ? idx1 : idx2) - i;
  }
  for (int bt = 1; bt < LIM; ++bt) {
    for (int i = 0; i + (1 << (bt - 1)) < n; ++i) {
      if ((1 << bt) <= free_cit[i][0]) {
        ll time = l[i] + (1 << bt);
        ll v = adjust(i + (1 << bt) - 1, time - 1);
        ansl[i][bt] = (Pair){v, time - v};
      } else {
        if (free_cit[i][0] <= (1 << (bt - 1))) {
          Pair tmp1 = ansl[i][bt - 1];
          Pair tmp2 = trans(i + (1 << (bt - 1)), bt - 1, tmp1.time);
          ansl[i][bt] = (Pair){tmp1.cost + tmp2.cost, tmp2.time};
        } else {
          Pair tmp1 = _ans(i + (1 << (bt - 1)), 1 << (bt - 1), ansl[i][bt - 1].time);
          ansl[i][bt] = (Pair){ansl[i][bt - 1].cost + tmp1.cost, tmp1.time};
        }
      }
      if ((1 << bt) <= free_cit[i][1]) {
        ll time = r[i] - 1 + (1 << bt);
        ll v = adjust(i + (1 << bt) - 1, time - 1);
        ansr[i][bt] = (Pair){v, time - v};
      } else {
        if (free_cit[i][1] <= (1 << (bt - 1))) {
          Pair tmp1 = ansr[i][bt - 1];
          Pair tmp2 = trans(i + (1 << (bt - 1)), bt - 1, tmp1.time);
          ansr[i][bt] = (Pair){tmp1.cost + tmp2.cost, tmp2.time};
        } else {
          Pair tmp2 = _ans(i + (1 << (bt - 1)), 1 << (bt - 1), ansr[i][bt - 1].time);
          ansr[i][bt] = (Pair){ansr[i][bt - 1].cost + tmp2.cost, tmp2.time};
        }
      }
      if ((1 << bt) <= free_cit[i][2]) {
        ll time = t[i] + (1 << bt);
        ll v = adjust(i + (1 << bt) - 1, time - 1);
        ansm[i][bt] = (Pair){v, time - v};
      } else {
        if (free_cit[i][2] <= (1 << (bt - 1))) {
          Pair tmp1 = ansm[i][bt - 1];
          Pair tmp2 = trans(i + (1 << (bt - 1)), bt - 1, tmp1.time);
          ansm[i][bt] = (Pair){tmp1.cost + tmp2.cost, tmp2.time};
        } else {
          Pair tmp3 = _ans(i + (1 << (bt - 1)), 1 << (bt - 1), ansm[i][bt - 1].time);
          ansm[i][bt] = (Pair){ansm[i][bt - 1].cost + tmp3.cost, tmp3.time};
        }
      }
    }
  }
  for (int k = 0; k < qsize; ++k) {
    ll a = queries[k].a, b = queries[k].b, c = queries[k].c, d = queries[k].d;
    int i = queries[k].i;
    Pair res = _ans(a, c - a - 1, b);
    ll cost = res.cost, time = res.time;
    if (time < l[c - 1])
      time = l[c - 1];
    else if (time > r[c - 1] - 1) {
      cost += time - r[c - 1] + 1;
      time = r[c - 1] - 1;
    }
    if (++time > d)
      cost += time - d;
    if (cost > ans[i])
      ans[i] = cost;
  }
}

int main() {
  scanf("%d %d", &n, &q);
  l[n - 1] = INF;
  r[n - 1] = INF + 1;
  l[n] = r[n] = INF + 2;
  for (int i = 0; i < n - 1; ++i) {
    scanf("%lld %lld", &l[i], &r[i]);
  }
  Query *q1 = (Query *)malloc(q * sizeof(Query));
  Query *q2 = (Query *)malloc(q * sizeof(Query));
  int q1s = 0, q2s = 0;
  for (int i = 0, a, b, c, d, t; i < q; ++i) {
    scanf("%d %d %d %d %d", &t, &a, &b, &c, &d);
    --a, --c;
    if (a == c)
      continue;
    if (a < c) {
      q1[q1s++] = (Query){a, b, c, d, i};
    } else {
      q2[q2s++] = (Query){n - a - 1, b, n - c - 1, d, i};
    }
  }
  solve(q1, q1s);
  for (int i = 0; i < n - 1 - i; ++i) {
    ll tmp = l[i];
    l[i] = l[n - 2 - i];
    l[n - 2 - i] = tmp;
    tmp = r[i];
    r[i] = r[n - 2 - i];
    r[n - 2 - i] = tmp;
  }
  solve(q2, q2s);
  for (int i = 0; i < q; ++i) {
    printf("%lld\n", ans[i]);
  }
  free(q1);
  free(q2);
  return 0;
}

Compilation message (stderr)

timeleap.c: In function 'main':
timeleap.c:208:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  208 |   scanf("%d %d", &n, &q);
      |   ^~~~~~~~~~~~~~~~~~~~~~
timeleap.c:213:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  213 |     scanf("%lld %lld", &l[i], &r[i]);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.c:219:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  219 |     scanf("%d %d %d %d %d", &t, &a, &b, &c, &d);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 30
• Subtask 3: 0 / 66