oj.uz

Submission #484415

# Submission time Handle Problem Language Result Execution time Memory
484415 2021-11-03T09:23:49 Z HolyK Progression (NOI20_progression) C++17
100 / 100
 1571 ms 160776 KB 
// Author:  HolyK
// Created: Wed Nov  3 16:27:37 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;

constexpr int N(3e5 + 5);
int n, a[N];

#define ls o << 1
#define rs o << 1 | 1

struct SegTreeA {
  struct Line {
    LL k, b;
    Line(LL k = 0, LL b = 0) : k(k), b(b) {}
    bool empty() const {
      return k == 0 && b == 0;
    }
    void operator+=(const Line &r) {
      k += r.k, b += r.b;
    }
    LL f(LL x) {
      return k * x + b;
    }
  } t[N << 2], add[N << 2], cov[N << 2];
  bool isCov[N << 2];

  void applyAdd(int o, const Line &r) {
    t[o] += r;
    add[o] += r;
  }
  void applyCov(int o, const Line &r) {
    t[o] = r, add[o] = Line(), cov[o] = r;
    isCov[o] = true;
  }

  void pushdown(int o) {
    if (isCov[o]) {
      applyCov(ls, cov[o]), applyCov(rs, cov[o]);
      isCov[o] = false;
    }
  
    if (!add[o].empty()) {
      applyAdd(ls, add[o]), applyAdd(rs, add[o]);
      add[o] = Line();
    }
  }

  void build(int o, int l, int r) {
    if (l == r) {
      t[o] = Line(0, a[l]);
      return;
    }
    int m = l + r >> 1;
    build(ls, l, m), build(rs, m + 1, r);
  }

  LL ask(int o, int l, int r, int x) {
    if (l == r) return t[o].f(l);
    int m = l + r >> 1;
    pushdown(o);
    return x <= m ? ask(ls, l, m, x) : ask(rs, m + 1, r, x);
  }

  void rangeAdd(int o, int l, int r, int x, int y, const Line &z) {
    if (x <= l && r <= y) return applyAdd(o, z);
    int m = l + r >> 1;
    pushdown(o);
    if (x <= m) rangeAdd(ls, l, m, x, y, z);
    if (y > m) rangeAdd(rs, m + 1, r, x, y, z);
  }

  void rangeCov(int o, int l, int r, int x, int y, const Line &z) {
    if (x <= l && r <= y) return applyCov(o, z);
    int m = l + r >> 1;
    pushdown(o);
    if (x <= m) rangeCov(ls, l, m, x, y, z);
    if (y > m) rangeCov(rs, m + 1, r, x, y, z);
  }
} sta;

struct SegTreeB {
  struct Info {
    int l;
    LL x;
    friend Info operator+(const Info &a, const Info &b) {
      if (a.l > 0 && b.l > 0 && a.x == b.x) return {a.l + b.l, a.x};
      return {-1000000000, 0};
    }
    bool operator<(const Info &r) const {
      return l < r.l;
    }
    void operator+=(LL r) {
      x += r;
    }
  };
  
  struct Node {
    Info l, r, t, ans;
    int len;
    friend Node operator+(const Node &a, const Node &b) {
      return {
        std::max(a.l, a.t + b.l),
        std::max(b.r, b.t + a.r),
        a.t + b.t,
        std::max({a.ans, b.ans, a.r + b.l}),
        a.len + b.len
      };
    }
  } t[N << 2];

  LL cov[N << 2], add[N << 2];
  bool isCov[N << 2];
  
  void applyCov(int o, LL x) {
    t[o].l = t[o].r = t[o].t = t[o].ans = {t[o].len, x};
    cov[o] = x;
    isCov[o] = true;
    add[o] = 0;
  }
  void applyAdd(int o, LL x) {
    t[o].l += x, t[o].r += x, t[o].t += x, t[o].ans += x;
    add[o] += x;
  }

  void pushdown(int o) {
    if (isCov[o]) {
      applyCov(ls, cov[o]), applyCov(rs, cov[o]);
      isCov[o] = false;
    }
    
    if (add[o]) {
      applyAdd(ls, add[o]), applyAdd(rs, add[o]);
      add[o] = 0;
    }
  }

  
  
  void pushup(int o) {
    t[o] = t[ls] + t[rs];
  }
  
  void build(int o, int l, int r) {
    t[o].len = r - l + 1;
    if (l == r) {
      applyCov(o, a[l] - a[l - 1]);
      return;
    }
    int m = l + r >> 1;
    build(ls, l, m), build(rs, m + 1, r);
    pushup(o);
  }

   void rangeAdd(int o, int l, int r, int x, int y, LL z) {
    if (x <= l && r <= y) return applyAdd(o, z);
    int m = l + r >> 1;
    pushdown(o);
    if (x <= m) rangeAdd(ls, l, m, x, y, z);
    if (y > m) rangeAdd(rs, m + 1, r, x, y, z);
    pushup(o);
  }

  void rangeCov(int o, int l, int r, int x, int y, LL z) {
    if (x <= l && r <= y) return applyCov(o, z);
    int m = l + r >> 1;
    pushdown(o);
    if (x <= m) rangeCov(ls, l, m, x, y, z);
    if (y > m) rangeCov(rs, m + 1, r, x, y, z);
    pushup(o);
  }

  Node ask(int o, int l, int r, int x, int y) {
    if (x <= l && r <= y) return t[o];
    int m = l + r >> 1;
    pushdown(o);
    if (y <= m) return ask(ls, l, m, x, y);
    if (x > m) return ask(rs, m + 1, r, x, y);
    return ask(ls, l, m, x, y) + ask(rs, m + 1, r, x, y);
  }
} stb;


int main() {
  // freopen("t.in", "r", stdin);
  // freopen(".out", "w", stdout);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int q;
  std::cin >> n >> q;
  for (int i = 1; i <= n; i++) std::cin >> a[i];
  sta.build(1, 1, n);
  stb.build(1, 1, n);
  // std::cerr << "build end\n";
  while (q--) {
    int opt, l, r, x, y;
    std::cin >> opt >> l >> r;
    if (opt == 3) {
      std::cout << (l < r ? stb.ask(1, 1, n, l + 1, r).ans.l : 0) + 1 << "\n";
    } else {
      std::cin >> x >> y;
      // std::cerr << opt << "\n";
      if (opt == 1) {
        sta.rangeAdd(1, 1, n, l, r, SegTreeA::Line(y, x - 1LL * l * y));
        // std::cerr << "rg\n";
        if (l < r) stb.rangeAdd(1, 1, n, l + 1, r, y);
      } else {
        sta.rangeCov(1, 1, n, l, r, SegTreeA::Line(y, x - 1LL * l * y));
        if (l < r) stb.rangeCov(1, 1, n, l + 1, r, y);
      }

#define ask(x) sta.ask(1, 1, n, x)
      stb.rangeCov(1, 1, n, l, l, ask(l) - ask(l - 1));
      if (r < n) {
        stb.rangeCov(1, 1, n, r + 1, r + 1, ask(r + 1) - ask(r));
      }
      
      // for (int i = 1; i <= n; i++) {
      //   std::cerr << ask(i) << " \n"[i == n];
      // }
      
#undef ask
    }
  }
  return 0;
}

Compilation message

Progression.cpp: In member function 'void SegTreeA::build(int, int, int)':
Progression.cpp:64:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |     int m = l + r >> 1;
      |             ~~^~~
Progression.cpp: In member function 'LL SegTreeA::ask(int, int, int, int)':
Progression.cpp:70:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |     int m = l + r >> 1;
      |             ~~^~~
Progression.cpp: In member function 'void SegTreeA::rangeAdd(int, int, int, int, int, const SegTreeA::Line&)':
Progression.cpp:77:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |     int m = l + r >> 1;
      |             ~~^~~
Progression.cpp: In member function 'void SegTreeA::rangeCov(int, int, int, int, int, const SegTreeA::Line&)':
Progression.cpp:85:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |     int m = l + r >> 1;
      |             ~~^~~
Progression.cpp: In member function 'void SegTreeB::build(int, int, int)':
Progression.cpp:160:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  160 |     int m = l + r >> 1;
      |             ~~^~~
Progression.cpp: In member function 'void SegTreeB::rangeAdd(int, int, int, int, int, LL)':
Progression.cpp:167:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  167 |     int m = l + r >> 1;
      |             ~~^~~
Progression.cpp: In member function 'void SegTreeB::rangeCov(int, int, int, int, int, LL)':
Progression.cpp:176:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  176 |     int m = l + r >> 1;
      |             ~~^~~
Progression.cpp: In member function 'SegTreeB::Node SegTreeB::ask(int, int, int, int, int)':
Progression.cpp:185:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  185 |     int m = l + r >> 1;
      |             ~~^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 145600 KB Output is correct
2 Correct 150 ms 56936 KB Output is correct
3 Correct 150 ms 56960 KB Output is correct
4 Correct 151 ms 56900 KB Output is correct
5 Correct 152 ms 56988 KB Output is correct
6 Correct 154 ms 57128 KB Output is correct
7 Correct 149 ms 56928 KB Output is correct
8 Correct 21 ms 56652 KB Output is correct
9 Correct 24 ms 56692 KB Output is correct
10 Correct 21 ms 56632 KB Output is correct
11 Correct 455 ms 153576 KB Output is correct
12 Correct 440 ms 153408 KB Output is correct
13 Correct 456 ms 153828 KB Output is correct
14 Correct 452 ms 153924 KB Output is correct
15 Correct 441 ms 153716 KB Output is correct
16 Correct 453 ms 153444 KB Output is correct
17 Correct 433 ms 153416 KB Output is correct
18 Correct 437 ms 153532 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56780 KB Output is correct
2 Correct 23 ms 56664 KB Output is correct
3 Correct 24 ms 56656 KB Output is correct
4 Correct 23 ms 56652 KB Output is correct
5 Correct 22 ms 56696 KB Output is correct
6 Correct 22 ms 56664 KB Output is correct
7 Correct 22 ms 56644 KB Output is correct
8 Correct 25 ms 56908 KB Output is correct
9 Correct 27 ms 56896 KB Output is correct
10 Correct 24 ms 56888 KB Output is correct
11 Correct 24 ms 56916 KB Output is correct
12 Correct 24 ms 56828 KB Output is correct
13 Correct 23 ms 56772 KB Output is correct
14 Correct 23 ms 56884 KB Output is correct
15 Correct 24 ms 56908 KB Output is correct
16 Correct 24 ms 56792 KB Output is correct
17 Correct 25 ms 56812 KB Output is correct
18 Correct 27 ms 56908 KB Output is correct
19 Correct 23 ms 56696 KB Output is correct
20 Correct 23 ms 56700 KB Output is correct
21 Correct 23 ms 56700 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 145792 KB Output is correct
2 Correct 95 ms 57188 KB Output is correct
3 Correct 93 ms 57240 KB Output is correct
4 Correct 88 ms 57324 KB Output is correct
5 Correct 101 ms 57284 KB Output is correct
6 Correct 100 ms 57276 KB Output is correct
7 Correct 100 ms 57252 KB Output is correct
8 Correct 22 ms 56652 KB Output is correct
9 Correct 23 ms 56708 KB Output is correct
10 Correct 23 ms 56652 KB Output is correct
11 Correct 317 ms 150720 KB Output is correct
12 Correct 281 ms 151868 KB Output is correct
13 Correct 333 ms 150460 KB Output is correct
14 Correct 329 ms 150468 KB Output is correct
15 Correct 281 ms 151796 KB Output is correct
16 Correct 330 ms 152388 KB Output is correct
17 Correct 327 ms 152448 KB Output is correct
18 Correct 351 ms 152508 KB Output is correct
19 Correct 302 ms 151988 KB Output is correct
20 Correct 279 ms 151836 KB Output is correct
21 Correct 285 ms 151748 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 146116 KB Output is correct
2 Correct 180 ms 57156 KB Output is correct
3 Correct 171 ms 56984 KB Output is correct
4 Correct 167 ms 56932 KB Output is correct
5 Correct 172 ms 57020 KB Output is correct
6 Correct 177 ms 57028 KB Output is correct
7 Correct 173 ms 56924 KB Output is correct
8 Correct 23 ms 56652 KB Output is correct
9 Correct 24 ms 56780 KB Output is correct
10 Correct 23 ms 56596 KB Output is correct
11 Correct 734 ms 152252 KB Output is correct
12 Correct 741 ms 155484 KB Output is correct
13 Correct 745 ms 152228 KB Output is correct
14 Correct 739 ms 152284 KB Output is correct
15 Correct 694 ms 155332 KB Output is correct
16 Correct 755 ms 155460 KB Output is correct
17 Correct 746 ms 155544 KB Output is correct
18 Correct 760 ms 155844 KB Output is correct
19 Correct 721 ms 155660 KB Output is correct
20 Correct 742 ms 155644 KB Output is correct
21 Correct 728 ms 155400 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 145792 KB Output is correct
2 Correct 95 ms 57188 KB Output is correct
3 Correct 93 ms 57240 KB Output is correct
4 Correct 88 ms 57324 KB Output is correct
5 Correct 101 ms 57284 KB Output is correct
6 Correct 100 ms 57276 KB Output is correct
7 Correct 100 ms 57252 KB Output is correct
8 Correct 22 ms 56652 KB Output is correct
9 Correct 23 ms 56708 KB Output is correct
10 Correct 23 ms 56652 KB Output is correct
11 Correct 317 ms 150720 KB Output is correct
12 Correct 281 ms 151868 KB Output is correct
13 Correct 333 ms 150460 KB Output is correct
14 Correct 329 ms 150468 KB Output is correct
15 Correct 281 ms 151796 KB Output is correct
16 Correct 330 ms 152388 KB Output is correct
17 Correct 327 ms 152448 KB Output is correct
18 Correct 351 ms 152508 KB Output is correct
19 Correct 302 ms 151988 KB Output is correct
20 Correct 279 ms 151836 KB Output is correct
21 Correct 285 ms 151748 KB Output is correct
22 Correct 1092 ms 156192 KB Output is correct
23 Correct 183 ms 59952 KB Output is correct
24 Correct 188 ms 59976 KB Output is correct
25 Correct 181 ms 59844 KB Output is correct
26 Correct 179 ms 59904 KB Output is correct
27 Correct 179 ms 59968 KB Output is correct
28 Correct 187 ms 59880 KB Output is correct
29 Correct 22 ms 56652 KB Output is correct
30 Correct 23 ms 56636 KB Output is correct
31 Correct 23 ms 56632 KB Output is correct
32 Correct 1053 ms 153364 KB Output is correct
33 Correct 1027 ms 156204 KB Output is correct
34 Correct 1228 ms 153432 KB Output is correct
35 Correct 1049 ms 153304 KB Output is correct
36 Correct 747 ms 153216 KB Output is correct
37 Correct 815 ms 153260 KB Output is correct
38 Correct 757 ms 153284 KB Output is correct
39 Correct 1084 ms 156512 KB Output is correct
40 Correct 1114 ms 156396 KB Output is correct
41 Correct 1108 ms 156300 KB Output is correct
42 Correct 1105 ms 156164 KB Output is correct
43 Correct 1049 ms 156408 KB Output is correct
44 Correct 1044 ms 156100 KB Output is correct
45 Correct 1058 ms 156100 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 145600 KB Output is correct
2 Correct 150 ms 56936 KB Output is correct
3 Correct 150 ms 56960 KB Output is correct
4 Correct 151 ms 56900 KB Output is correct
5 Correct 152 ms 56988 KB Output is correct
6 Correct 154 ms 57128 KB Output is correct
7 Correct 149 ms 56928 KB Output is correct
8 Correct 21 ms 56652 KB Output is correct
9 Correct 24 ms 56692 KB Output is correct
10 Correct 21 ms 56632 KB Output is correct
11 Correct 455 ms 153576 KB Output is correct
12 Correct 440 ms 153408 KB Output is correct
13 Correct 456 ms 153828 KB Output is correct
14 Correct 452 ms 153924 KB Output is correct
15 Correct 441 ms 153716 KB Output is correct
16 Correct 453 ms 153444 KB Output is correct
17 Correct 433 ms 153416 KB Output is correct
18 Correct 437 ms 153532 KB Output is correct
19 Correct 25 ms 56780 KB Output is correct
20 Correct 23 ms 56664 KB Output is correct
21 Correct 24 ms 56656 KB Output is correct
22 Correct 23 ms 56652 KB Output is correct
23 Correct 22 ms 56696 KB Output is correct
24 Correct 22 ms 56664 KB Output is correct
25 Correct 22 ms 56644 KB Output is correct
26 Correct 25 ms 56908 KB Output is correct
27 Correct 27 ms 56896 KB Output is correct
28 Correct 24 ms 56888 KB Output is correct
29 Correct 24 ms 56916 KB Output is correct
30 Correct 24 ms 56828 KB Output is correct
31 Correct 23 ms 56772 KB Output is correct
32 Correct 23 ms 56884 KB Output is correct
33 Correct 24 ms 56908 KB Output is correct
34 Correct 24 ms 56792 KB Output is correct
35 Correct 25 ms 56812 KB Output is correct
36 Correct 27 ms 56908 KB Output is correct
37 Correct 23 ms 56696 KB Output is correct
38 Correct 23 ms 56700 KB Output is correct
39 Correct 23 ms 56700 KB Output is correct
40 Correct 265 ms 145792 KB Output is correct
41 Correct 95 ms 57188 KB Output is correct
42 Correct 93 ms 57240 KB Output is correct
43 Correct 88 ms 57324 KB Output is correct
44 Correct 101 ms 57284 KB Output is correct
45 Correct 100 ms 57276 KB Output is correct
46 Correct 100 ms 57252 KB Output is correct
47 Correct 22 ms 56652 KB Output is correct
48 Correct 23 ms 56708 KB Output is correct
49 Correct 23 ms 56652 KB Output is correct
50 Correct 317 ms 150720 KB Output is correct
51 Correct 281 ms 151868 KB Output is correct
52 Correct 333 ms 150460 KB Output is correct
53 Correct 329 ms 150468 KB Output is correct
54 Correct 281 ms 151796 KB Output is correct
55 Correct 330 ms 152388 KB Output is correct
56 Correct 327 ms 152448 KB Output is correct
57 Correct 351 ms 152508 KB Output is correct
58 Correct 302 ms 151988 KB Output is correct
59 Correct 279 ms 151836 KB Output is correct
60 Correct 285 ms 151748 KB Output is correct
61 Correct 729 ms 146116 KB Output is correct
62 Correct 180 ms 57156 KB Output is correct
63 Correct 171 ms 56984 KB Output is correct
64 Correct 167 ms 56932 KB Output is correct
65 Correct 172 ms 57020 KB Output is correct
66 Correct 177 ms 57028 KB Output is correct
67 Correct 173 ms 56924 KB Output is correct
68 Correct 23 ms 56652 KB Output is correct
69 Correct 24 ms 56780 KB Output is correct
70 Correct 23 ms 56596 KB Output is correct
71 Correct 734 ms 152252 KB Output is correct
72 Correct 741 ms 155484 KB Output is correct
73 Correct 745 ms 152228 KB Output is correct
74 Correct 739 ms 152284 KB Output is correct
75 Correct 694 ms 155332 KB Output is correct
76 Correct 755 ms 155460 KB Output is correct
77 Correct 746 ms 155544 KB Output is correct
78 Correct 760 ms 155844 KB Output is correct
79 Correct 721 ms 155660 KB Output is correct
80 Correct 742 ms 155644 KB Output is correct
81 Correct 728 ms 155400 KB Output is correct
82 Correct 1092 ms 156192 KB Output is correct
83 Correct 183 ms 59952 KB Output is correct
84 Correct 188 ms 59976 KB Output is correct
85 Correct 181 ms 59844 KB Output is correct
86 Correct 179 ms 59904 KB Output is correct
87 Correct 179 ms 59968 KB Output is correct
88 Correct 187 ms 59880 KB Output is correct
89 Correct 22 ms 56652 KB Output is correct
90 Correct 23 ms 56636 KB Output is correct
91 Correct 23 ms 56632 KB Output is correct
92 Correct 1053 ms 153364 KB Output is correct
93 Correct 1027 ms 156204 KB Output is correct
94 Correct 1228 ms 153432 KB Output is correct
95 Correct 1049 ms 153304 KB Output is correct
96 Correct 747 ms 153216 KB Output is correct
97 Correct 815 ms 153260 KB Output is correct
98 Correct 757 ms 153284 KB Output is correct
99 Correct 1084 ms 156512 KB Output is correct
100 Correct 1114 ms 156396 KB Output is correct
101 Correct 1108 ms 156300 KB Output is correct
102 Correct 1105 ms 156164 KB Output is correct
103 Correct 1049 ms 156408 KB Output is correct
104 Correct 1044 ms 156100 KB Output is correct
105 Correct 1058 ms 156100 KB Output is correct
106 Correct 1571 ms 160404 KB Output is correct
107 Correct 241 ms 60100 KB Output is correct
108 Correct 242 ms 60172 KB Output is correct
109 Correct 241 ms 60100 KB Output is correct
110 Correct 24 ms 56652 KB Output is correct
111 Correct 24 ms 56728 KB Output is correct
112 Correct 23 ms 56652 KB Output is correct
113 Correct 1134 ms 156316 KB Output is correct
114 Correct 1107 ms 156384 KB Output is correct
115 Correct 1135 ms 156324 KB Output is correct
116 Correct 1044 ms 156128 KB Output is correct
117 Correct 1472 ms 160776 KB Output is correct
118 Correct 1033 ms 156240 KB Output is correct
119 Correct 1024 ms 156104 KB Output is correct
120 Correct 323 ms 152692 KB Output is correct
121 Correct 347 ms 152556 KB Output is correct
122 Correct 334 ms 152644 KB Output is correct
123 Correct 282 ms 151828 KB Output is correct
124 Correct 280 ms 151792 KB Output is correct
125 Correct 303 ms 151732 KB Output is correct
126 Correct 1513 ms 157160 KB Output is correct
127 Correct 1470 ms 157108 KB Output is correct
128 Correct 1490 ms 160448 KB Output is correct
129 Correct 1472 ms 157140 KB Output is correct
130 Correct 994 ms 157188 KB Output is correct
131 Correct 954 ms 157224 KB Output is correct
132 Correct 891 ms 157252 KB Output is correct
133 Correct 1536 ms 160568 KB Output is correct
134 Correct 1550 ms 160396 KB Output is correct
135 Correct 1500 ms 160452 KB Output is correct
136 Correct 238 ms 60100 KB Output is correct
137 Correct 237 ms 60084 KB Output is correct
138 Correct 241 ms 60272 KB Output is correct