oj.uz

Submission #200766

# Submission time Handle Problem Language Result Execution time Memory
200766 2020-02-08T06:11:31 Z EntityIT Bitaro, who Leaps through Time (JOI19_timeleap) C++14
0 / 100
 729 ms 46780 KB 
#include<bits/stdc++.h>

using namespace std;

#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);
  }
};

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

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #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(0, 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(0, tmp.cur - (d - (a < c ? c : n - 1 - c) ) ) << '\n';
      }
    }
  }

  return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Incorrect 12 ms 504 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 729 ms 46780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Incorrect 12 ms 504 KB Output isn't correct
12 Halted 0 ms 0 KB -