oj.uz

Submission #200770

# Submission time Handle Problem Language Result Execution time Memory
200770 2020-02-08T06:16:06 Z EntityIT Bitaro, who Leaps through Time (JOI19_timeleap) C++14
100 / 100
 928 ms 114716 KB 
#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.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 4 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 Correct 6 ms 632 KB Output is correct
12 Correct 6 ms 760 KB Output is correct
13 Correct 7 ms 760 KB Output is correct
14 Correct 7 ms 632 KB Output is correct
15 Correct 7 ms 760 KB Output is correct
16 Correct 7 ms 632 KB Output is correct
17 Correct 7 ms 760 KB Output is correct
18 Correct 8 ms 632 KB Output is correct
19 Correct 6 ms 632 KB Output is correct
20 Correct 7 ms 632 KB Output is correct
21 Correct 7 ms 632 KB Output is correct
22 Correct 6 ms 636 KB Output is correct
23 Correct 7 ms 756 KB Output is correct
24 Correct 6 ms 632 KB Output is correct
25 Correct 7 ms 760 KB Output is correct
26 Correct 7 ms 632 KB Output is correct
27 Correct 7 ms 632 KB Output is correct
28 Correct 7 ms 632 KB Output is correct
29 Correct 7 ms 632 KB Output is correct
30 Correct 7 ms 636 KB Output is correct
31 Correct 7 ms 632 KB Output is correct
32 Correct 6 ms 636 KB Output is correct
33 Correct 7 ms 760 KB Output is correct
34 Correct 7 ms 632 KB Output is correct
35 Correct 7 ms 760 KB Output is correct
36 Correct 6 ms 760 KB Output is correct
37 Correct 7 ms 632 KB Output is correct
38 Correct 6 ms 632 KB Output is correct
39 Correct 7 ms 632 KB Output is correct
40 Correct 7 ms 760 KB Output is correct
41 Correct 5 ms 376 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 821 ms 90588 KB Output is correct
2 Correct 814 ms 100712 KB Output is correct
3 Correct 850 ms 101864 KB Output is correct
4 Correct 809 ms 99064 KB Output is correct
5 Correct 829 ms 105976 KB Output is correct
6 Correct 823 ms 104184 KB Output is correct
7 Correct 830 ms 107232 KB Output is correct
8 Correct 844 ms 111608 KB Output is correct
9 Correct 771 ms 100088 KB Output is correct
10 Correct 841 ms 106852 KB Output is correct
11 Correct 828 ms 106076 KB Output is correct
12 Correct 871 ms 113124 KB Output is correct
13 Correct 846 ms 114716 KB Output is correct
14 Correct 5 ms 376 KB Output is correct

Subtask #3
66.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 4 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 Correct 6 ms 632 KB Output is correct
12 Correct 6 ms 760 KB Output is correct
13 Correct 7 ms 760 KB Output is correct
14 Correct 7 ms 632 KB Output is correct
15 Correct 7 ms 760 KB Output is correct
16 Correct 7 ms 632 KB Output is correct
17 Correct 7 ms 760 KB Output is correct
18 Correct 8 ms 632 KB Output is correct
19 Correct 6 ms 632 KB Output is correct
20 Correct 7 ms 632 KB Output is correct
21 Correct 7 ms 632 KB Output is correct
22 Correct 6 ms 636 KB Output is correct
23 Correct 7 ms 756 KB Output is correct
24 Correct 6 ms 632 KB Output is correct
25 Correct 7 ms 760 KB Output is correct
26 Correct 7 ms 632 KB Output is correct
27 Correct 7 ms 632 KB Output is correct
28 Correct 7 ms 632 KB Output is correct
29 Correct 7 ms 632 KB Output is correct
30 Correct 7 ms 636 KB Output is correct
31 Correct 7 ms 632 KB Output is correct
32 Correct 6 ms 636 KB Output is correct
33 Correct 7 ms 760 KB Output is correct
34 Correct 7 ms 632 KB Output is correct
35 Correct 7 ms 760 KB Output is correct
36 Correct 6 ms 760 KB Output is correct
37 Correct 7 ms 632 KB Output is correct
38 Correct 6 ms 632 KB Output is correct
39 Correct 7 ms 632 KB Output is correct
40 Correct 7 ms 760 KB Output is correct
41 Correct 5 ms 376 KB Output is correct
42 Correct 821 ms 90588 KB Output is correct
43 Correct 814 ms 100712 KB Output is correct
44 Correct 850 ms 101864 KB Output is correct
45 Correct 809 ms 99064 KB Output is correct
46 Correct 829 ms 105976 KB Output is correct
47 Correct 823 ms 104184 KB Output is correct
48 Correct 830 ms 107232 KB Output is correct
49 Correct 844 ms 111608 KB Output is correct
50 Correct 771 ms 100088 KB Output is correct
51 Correct 841 ms 106852 KB Output is correct
52 Correct 828 ms 106076 KB Output is correct
53 Correct 871 ms 113124 KB Output is correct
54 Correct 846 ms 114716 KB Output is correct
55 Correct 5 ms 376 KB Output is correct
56 Correct 823 ms 101956 KB Output is correct
57 Correct 813 ms 95648 KB Output is correct
58 Correct 868 ms 104644 KB Output is correct
59 Correct 853 ms 105516 KB Output is correct
60 Correct 816 ms 98304 KB Output is correct
61 Correct 859 ms 108488 KB Output is correct
62 Correct 877 ms 108072 KB Output is correct
63 Correct 882 ms 107728 KB Output is correct
64 Correct 928 ms 108596 KB Output is correct
65 Correct 880 ms 103296 KB Output is correct
66 Correct 865 ms 103864 KB Output is correct
67 Correct 856 ms 108012 KB Output is correct
68 Correct 823 ms 99568 KB Output is correct
69 Correct 862 ms 111212 KB Output is correct
70 Correct 827 ms 98944 KB Output is correct
71 Correct 847 ms 94996 KB Output is correct
72 Correct 825 ms 98908 KB Output is correct
73 Correct 874 ms 108508 KB Output is correct
74 Correct 857 ms 109032 KB Output is correct
75 Correct 897 ms 110852 KB Output is correct
76 Correct 877 ms 111768 KB Output is correct
77 Correct 5 ms 376 KB Output is correct