Submission #219693

#	Time	Username	Problem	Language	Result	Execution time	Memory
219693		rama_pang	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	100 / 100	744 ms	42232 KiB

timeleap

#include <bits/stdc++.h>
using namespace std;

class TimeLeap { // segment tree
 private:
  struct Node {
    bool collision;

    int st, et; // interval where if we start in the beginning of the segment in this time interval, we do not need to 
                // timeleap at all until the collision

    long long timeleap; // the number of timeleaps needed to get from just the collision to the end of the segment. We 
                        // start at et if we collide with an L, or start at st if we collide with an R. Note that this 
                        // start points will be travelled through no matter what.

    int endtime; // endtime if there is a collision (since if there is, the endtime is forced)

    Node() {}
    Node(bool c, int s, int e, long long t, int et) : collision(c), st(s), et(e), timeleap(t), endtime(et) {}

    long long Travel(int &t) { // how many timeleaps are needed (note that t is modified to become the final time)
      long long res;
      if (!collision) { // we do not need to timeleap once we are in interval [st, et]
        if (t > et) { // travel back to et, then we do not need to timeleap again 
                      // (this is optimal since et is the last time where we do not need to timleap)
          res = t - et;
          t = et;
        } else { // we do not need to timeleap
          res = 0;
          t = max(t, st);
        }
      } else { // we collideR, so we first go to st/et from before collision then adding the rest of timeleaps
        res = max(t - st, 0) + timeleap;
        t = endtime;
      }
      return res;
    }

    friend Node merge(Node a, Node b) {
      Node res;
      if (!a.collision && !b.collision) {
        if (max(a.st, b.st) <= min(a.et, b.et)) { // no collision
          res = Node(false, max(a.st, b.st), min(a.et, b.et), 0, -1);
        } else if (a.et < b.st) { // there is a new collision with L
          res.collision = true;
          res.st = res.et = res.endtime = a.et;
          res.timeleap = b.Travel(res.endtime);
        } else if (a.st > b.et) { // there is a new collision with R
          res.collision = true;
          res.st = res.et = res.endtime = a.st;
          res.timeleap = b.Travel(res.endtime);
        } 
      } else if (a.collision) { // we collide in a first, so we simply add b to the answer if we travel from a.endtime
        res = a;
        res.timeleap += b.Travel(res.endtime);
      } else if (b.collision) { // we collide in b first
        res = b;
        if (a.et < b.st) {
          res.st = res.et = res.endtime = a.et;
          res.timeleap = b.Travel(res.endtime);
        } else if (a.st > b.st) {
          res.st = res.et = res.endtime = a.st;
          res.timeleap = b.Travel(res.endtime);
        }
      }
      return res;
    }
  };

  int sz;
  vector<Node> tree;

  void Update(int n, int tl, int tr, int pos, int newL, int newR) {
    if (tl == tr) return void(tree[n] = Node(false, newL, newR, 0, -1));
    int mid = (tl + tr) / 2;
    int lc = n + 1;
    int rc = n + 2 * (mid - tl + 1);
    if (pos <= mid) {
      Update(lc, tl, mid, pos, newL, newR);
    } else {
      Update(rc, mid + 1, tr, pos, newL, newR);
    }
    tree[n] = merge(tree[lc], tree[rc]);
  }

  long long Query(int n, int tl, int tr, int l, int r, int &t) {
    if (tr < l || r < tl || tl > tr || l > r) return 0;
    if (l <= tl && tr <= r) return tree[n].Travel(t);
    int mid = (tl + tr) / 2;
    int lc = n + 1;
    int rc = n + 2 * (mid - tl + 1);
    long long res = 0;
    res += Query(lc, tl, mid, l, r, t);
    res += Query(rc, mid + 1, tr, l, r, t);
    return res;
  }

 public:
  TimeLeap(int n) : sz(n), tree(vector<Node>(2 * sz)) {}

  void Update(int pos, int newL, int newR) {
    return Update(1, 0, sz - 1, pos, newL, newR);
  }

  long long Query(int l, int r, int &t) {
    return Query(1, 0, sz - 1, l, r, t);
  }  
};

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

  int N, Q;
  cin >> N >> Q;
  N--;

  TimeLeap Left(N), Right(N);

  auto Update = [&](int pos, int newL, int newR) {
    Left.Update(pos, newL - pos, newR - pos - 1);
    pos = N - pos - 1;
    Right.Update(pos, newL - pos, newR - pos - 1);
    return;
  };

  auto Query = [&](int l, int r, int t1, int t2) {
    long long res = 0;
    if (l == r) {
      res = max(t1 - t2, 0);
    } else if (l < r) {
      t1 -= l, t2 -= r;
      res = Left.Query(l, --r, t1) + max(t1 - t2, 0);
    } else if (l > r) {
      l = N - l, r = N - r;
      t1 -= l, t2 -= r;
      res = Right.Query(l, --r, t1) + max(t1 - t2, 0);
    }
    return res;
  };

  for (int i = 0; i < N; i++) {
    int L, R;
    cin >> L >> R;
    Update(i, L, R);
  }

  for (int i = 0; i < Q; i++) {
    int T;
    cin >> T;
    if (T == 1) {
      int P, S, E;
      cin >> P >> S >> E;
      Update(--P, S, E);
    } else if (T == 2) {
      int A, B, C, D;
      cin >> A >> B >> C >> D;
      cout << Query(--A, --C, B, D) << "\n";
    }
  }

  return 0;
}

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