Submission #200770

#	Time	Username	Problem	Language	Result	Execution time	Memory
200770		EntityIT	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	100 / 100	928 ms	114716 KiB

timeleap

#include<bits/stdc++.h>

using namespace std;

#define int LL
#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

const int inf = 1e9;
mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );

int n;

struct Node {
  int be, en, cur, usage;
  bool flag;
  Node(int _be = 0, int _en = 0, int _cur = -inf, int _usage = 0, bool _flag = false)
      : be(_be), en(_en), cur(_cur), usage(_usage), flag(_flag) {}

  Node operator + (const Node &_) const {
    Node ret(0, 0, -inf, usage + _.usage);
    if (cur == -inf && _.cur == -inf) {
      ret.be = max(be, _.be);
      ret.en = min(en, _.en);
      if (ret.be >= ret.en) {
        ret.be = be; ret.en = en;
        if (en <= _.be) ret.cur = _.be;
        else ret.cur = _.en - 1, ret.usage += be - _.en + 1, ret.flag = true;
      }
    }
    else if (cur == -inf) {
      ret.be = max(be, _.be);
      ret.en = min(en, _.en);
      if (ret.be < ret.en) {
        ret.usage += (_.flag ? ret.be - _.be : 0);
        ret.flag = _.flag;
      }
      else {
        ret.be = be; ret.en = en;
        if (be >= _.en) ret.usage += be - _.en + 1 + (_.flag ? _.en - 1 - _.be : 0), ret.flag = true;
      }
      ret.cur = _.cur;
    }
    else if (_.cur == -inf) {
      ret.be = be; ret.en = en;
      if (_.be <= cur && cur < _.en) ret.cur = cur;
      else if (cur < _.be) ret.cur = _.be;
      else ret.cur = _.en - 1, ret.usage += cur - _.en + 1;
      ret.flag = flag;
    }
    else {
      ret.be = be; ret.en = en;
      ret.cur = _.cur;
      if (_.be <= cur && cur < _.en) ret.usage += _.flag ? cur - _.be : 0;
      else if (cur < _.be) {}
      else ret.usage += cur - _.en + 1 + (_.flag ? _.en - 1 - _.be : 0);
      ret.flag = flag;
    }
    return ret;
  }
};

struct It {
  #define lC (i << 1)
  #define rC (i << 1 | 1)
  #define Mid ( (Left + Right) >> 1)
  #define rt int i = 1, int Left = 0, int Right = n - 2

  vector<Node> node;
  It(int nNode) { node.assign(nNode, Node() ); }

  void upd(int pos, Node val, rt) {
    if (Left == Right) {
      node[i] = val;
      return ;
    }
    if (pos <= Mid) upd(pos, val, lC, Left, Mid);
    else upd(pos, val, rC, Mid + 1, Right);

    node[i] = node[lC] + node[rC];
  }
  Node get(int l, int r, rt) {
    if (l <= Left && Right <= r) return node[i];
    if (Mid < l) return get(l, r, rC, Mid + 1, Right);
    else if (r <= Mid) return get(l, r, lC, Left, Mid);
    else return get(l, r, lC, Left, Mid) + get(l, r, rC, Mid + 1, Right);
  }
};

int32_t main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  freopen("output", "w", stdout);
  #endif // FourLeafCLover

  cin >> n;
  int q; cin >> q;

  It it1( (n + 5) << 2),
     it2( (n + 5) << 2);
  for (int i = 0; i < n - 1; ++i) {
    int l, r; cin >> l >> r;
    it1.upd(i, Node(l - i, r - i) );
    it2.upd(n - 2 - i, Node(l - (n - 2 - i), r - (n - 2 - i) ) );
  }

  while (q--) {
    int type; cin >> type;
    if (type == 1) {
      int i, l, r; cin >> i >> l >> r; --i;
      it1.upd(i, Node(l - i, r - i) );
      it2.upd(n - 2 - i, Node(l - (n - 2 - i), r - (n - 2 - i) ) );
    }
    else {
      int a, b, c, d; cin >> a >> b >> c >> d; --a; --c;

      if (a == c) cout << max(0LL, b - d) << '\n';
      else {
        Node tmp;
        if (a < c) tmp = it1.get(a, c - 1);
        else tmp = it2.get(n - 1 - a, n - 1 - c - 1);

//        cerr << tmp.be << ' ' << tmp.en << ' ' << tmp.cur << ' ' << tmp.usage << ' ' << tmp.flag << '\n';

        int cur = b - (a < c ? a : n - 1 - a); //cerr << "cur = " << cur << '\n';
        if (tmp.be <= cur && cur < tmp.en) {
          tmp.usage += tmp.flag ? cur - tmp.be : 0;
          if (tmp.cur == -inf) tmp.cur = cur;
        }
        else if (cur < tmp.be) {
          if (tmp.cur == -inf) tmp.cur = tmp.be;
        }
        else {
          tmp.usage += cur - tmp.en + 1 + (tmp.flag ? tmp.en - 1 - tmp.be : 0);
          if (tmp.cur == -inf) tmp.cur = tmp.en - 1;
        }

        cout << tmp.usage + max(0LL, tmp.cur - (d - (a < c ? c : n - 1 - c) ) ) << '\n';
      }
    }
  }

  return 0;
}

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