Submission #1185864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185864		avighna	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	0 / 100	1813 ms	265936 KiB

timeleap

#include <stdio.h>
#include <stdlib.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 first, second;
} Pair;

ll l[N], r[N], ans[N], jump_min[N][LIM], jump_max[N][LIM];
Pair ansl[N][LIM], ansr[N][LIM];

int n, q;

Pair _ansl(int i, int x) {
  ll cost = 0, time = l[i];
  for (int bt = 0; bt < LIM; ++bt) {
    if (x & (1 << bt)) {
      cost += ansl[i][bt].first;
      time = ansl[i][bt].second;
      i += (1 << bt);
    }
  }
  Pair res = {cost, time};
  return res;
}

Pair _ansr(int i, int x) {
  ll cost = 0, time = r[i] - 1;
  for (int bt = 0; bt < LIM; ++bt) {
    if (x & (1 << bt)) {
      cost += ansr[i][bt].first;
      time = ansr[i][bt].second;
      i += (1 << bt);
    }
  }
  Pair res = {cost, time};
  return res;
}

Pair _ans(int i, int x, ll t) {
  int idx1 = i, 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;
  ll free_jumps = idx1 < idx2 ? idx1 : idx2;
  free_jumps -= 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 _ansl(idx1, x - free_jumps);
  } else {
    Pair p = _ansr(idx2, x - free_jumps);
    Pair res = {t + free_jumps - r[idx2] + p.first + 1, p.second};
    return res;
  }
}

void solve(Query *queries, int qsize) {
  for (int i = 0; i < n; ++i) {
    ll v1 = l[i] - r[i + 1] + 2 > 0 ? l[i] - r[i + 1] + 2 : 0;
    ll v2 = r[i] - r[i + 1] + 1 > 0 ? r[i] - r[i + 1] + 1 : 0;
    ansl[i][0] = (Pair){v1, l[i] - v1 + 1};
    ansr[i][0] = (Pair){v2, r[i] - v2};
    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];

        Pair tmp1 =
            _ans(i + (1 << (bt - 1)), 1 << (bt - 1), ansl[i][bt - 1].second);
        Pair tmp2 =
            _ans(i + (1 << (bt - 1)), 1 << (bt - 1), ansr[i][bt - 1].second);
        ansl[i][bt] = (Pair){ansl[i][bt - 1].first + tmp1.first, tmp1.second};
        ansr[i][bt] = (Pair){ansr[i][bt - 1].first + tmp2.first, tmp2.second};
      }
    }
  }
  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.first, time = res.second;
    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;
  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.cpp: In function 'int main()':
timeleap.cpp:140:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |   scanf("%d %d", &n, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~
timeleap.cpp:144:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |     scanf("%lld %lld", &l[i], &r[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:150:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |     scanf("%d %d %d %d %d", &t, &a, &b, &c, &d);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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