oj.uz

Submission #270669

# Submission time Handle Problem Language Result Execution time Memory
270669 2020-08-17T21:37:22 Z Haunted_Cpp Progression (NOI20_progression) C++17
57 / 100
 1334 ms 88184 KB 
/**
 *  author: Haunted_Cpp
**/
 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
 
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
 
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
 
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif

const long long INVALID = -1e18;

class SegmentTree {
private:
  struct Node {
    int pre, suf, best;
    long long lazy;
    long long lazy_set;
    long long delta_pre, delta_suf;
    long long sum;
    int t;
    Node() {
      pre = suf = best = 0;
      delta_pre = delta_suf = 0;
      t = 0;
      sum = 0;
      lazy_set = INVALID;
      lazy = INVALID;
    }
    void merge(Node l, Node r) {
      t = l.t + r.t;
      pre = l.pre;
      delta_pre = l.delta_pre;
      suf = r.suf;
      delta_suf = r.delta_suf;
      sum = l.sum + r.sum;
      if (l.pre == l.t && l.delta_pre == r.delta_pre) {
        pre = max(pre, l.pre + r.pre);
      }
      if (r.suf == r.t && l.delta_suf == r.delta_suf) {
        suf = max(suf, l.suf + r.suf);
      }
      best = max(l.best, r.best);
      if (l.delta_suf == r.delta_pre) {
        best = max(best, l.suf + r.pre);
      }
    }
  };
  const int LO, HI;
  vector<Node> seg;
  void build(int l, int r, int node, const vector<long long> &arr) {
    if (l == r) {
      seg[node].pre = seg[node].suf = seg[node].best = 1;
      seg[node].delta_pre = arr[l];
      seg[node].delta_suf = arr[l];
      seg[node].t = 1;
      seg[node].sum = arr[l];
      return;
    }
    const int mid = l + (r - l) / 2;
    build(l, mid, 2 * node + 1, arr);
    build(mid + 1, r, 2 * node + 2, arr);
    seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
  }
  Node range_query(int ql, int qr, int l, int r, int node) {
    push(l, r, node);
    if (l > qr || r < ql) {
     Node empty;
     empty.t = -1;
     return empty; 
    }
    if (l >= ql && r <= qr) {
      return seg[node];
    }
    const int mid = l + (r - l) / 2;
    Node esq = range_query(ql, qr, l, mid, 2 * node + 1);
    Node dir = range_query(ql, qr, mid + 1, r, 2 * node + 2);
    assert( (esq.t == -1 && dir.t == -1) == false);
    if (esq.t == -1) return dir;
    if (dir.t == -1) return esq;
    Node ans;
    ans.merge(esq, dir);
    return ans;
  }
  void push(int l, int r, int node) {
    if (seg[node].lazy_set != INVALID) {
      seg[node].delta_pre = seg[node].lazy_set;
      seg[node].delta_suf = seg[node].lazy_set;
      seg[node].pre = seg[node].suf = seg[node].best = r - l + 1;
      seg[node].sum = 1LL * (r - l + 1) * seg[node].lazy;
      if (l != r) {
        seg[2 * node + 1].lazy = INVALID;
        seg[2 * node + 1].lazy_set = seg[node].lazy_set;     
        seg[2 * node + 2].lazy = INVALID;
        seg[2 * node + 2].lazy_set = seg[node].lazy_set;
      }
      seg[node].lazy_set = INVALID;
    }
    if (seg[node].lazy != INVALID) {
      seg[node].delta_pre += seg[node].lazy;
      seg[node].delta_suf += seg[node].lazy;
      seg[node].sum += 1LL * (r - l + 1) * seg[node].lazy;
      if (l != r) {
        if (seg[2 * node + 1].lazy == INVALID) seg[2 * node + 1].lazy = 0;
        seg[2 * node + 1].lazy += seg[node].lazy;     
        if (seg[2 * node + 2].lazy == INVALID) seg[2 * node + 2].lazy = 0;
        seg[2 * node + 2].lazy += seg[node].lazy;
      }
      seg[node].lazy = INVALID;
    }
  }
  void range_update(int ql, int qr, long long delta, bool type, int l, int r, int node) {
    push(l, r, node);
    if (l > qr || r < ql) return;
    if (l >= ql && r <= qr) {
      if (type == 0) {
        seg[node].lazy = delta;
      } else {
        seg[node].lazy_set = delta;
      }
      push(l, r, node);
      return;
    }
    const int mid = l + (r - l) / 2;
    range_update(ql, qr, delta, type, l, mid, 2 * node + 1);
    range_update(ql, qr, delta, type, mid + 1, r, 2 * node + 2);
    seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
  }
public:
  SegmentTree(const vector<long long> &arr) : LO(0), HI((int)arr.size() - 1) {
    if (arr.empty()) return;
    seg.clear();
    seg.resize(4 * (int)arr.size());
    build(LO, HI, 0, arr);
  }
  int range_query(int lo, int hi) {
    if (lo > hi) return 0;
    Node ans = range_query(lo, hi, LO, HI, 0);
    return ans.best;
  }
  long long range_sum(int lo, int hi) {
    if (lo > hi) return 0;
    Node ans = range_query(lo, hi, LO, HI, 0);
    return ans.sum;
  }
  void range_update(int ql, int qr, long long delta) {
    if (ql > qr) return;
    range_update(ql, qr, delta, 0, LO, HI, 0);
  }
  void range_set(int ql, int qr, long long delta) {
    if (ql > qr) return;
    range_update(ql, qr, delta, 1, LO, HI, 0);
  }
};
 
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); 
  int n, q;
  cin >> n >> q;
  vector<int> arr(n);
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  vector<long long> diff(n - 1);
  for (int i = 1; i < n; i++) {
    diff[i - 1] = arr[i] - arr[i - 1];
  }
  if(diff.empty()) diff.emplace_back(0);
  SegmentTree seg(diff);
  long long first_element = arr[0];
  while(q--) {
    int t, lo, hi;
    cin >> t >> lo >> hi;
    --lo; hi -= 2; 
    if (t == 1) {
      int delta, d;
      cin >> delta >> d;
      if (lo == 0) {
        first_element += delta;
      }
      seg.range_update(lo, hi, +d);
     
      if (lo - 1 >= 0) {
        seg.range_update(lo - 1, lo - 1, +delta);
      }
      ++hi;
      if (hi < n - 1) {
        const long long sum = 1LL * d * (hi - lo); 
        seg.range_update(hi, hi, -delta - sum);
      }
    } else if (t == 2) {
      int delta, d;
      cin >> delta >> d;
      long long left_side = first_element + (lo - 1 >= 0 ? seg.range_sum(0, lo - 2) : 0);
      long long right_side =  (hi + 1 < n - 1 ? first_element + seg.range_sum(0, hi + 1) : -1);
      seg.range_set(lo, hi, d);
      if (lo == 0) {
        first_element = delta;
      }
      seg.range_set(lo, hi, d);
      if (lo - 1 >= 0) {
        const long long first_term = delta;
        seg.range_set(lo - 1, lo - 1, first_term - left_side);
      }
      ++hi;
      if (hi < n - 1) {
        const long long last_term = delta + 1LL * d * (hi - lo);
        seg.range_set(hi, hi, right_side - last_term);
      }
    } else {
      cout << seg.range_query(lo, hi) + 1 << '\n';
    }
  }
  return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 81016 KB Output is correct
2 Correct 97 ms 3576 KB Output is correct
3 Correct 98 ms 3552 KB Output is correct
4 Correct 97 ms 3576 KB Output is correct
5 Correct 97 ms 3704 KB Output is correct
6 Correct 98 ms 3704 KB Output is correct
7 Correct 97 ms 3580 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 392 KB Output is correct
11 Correct 206 ms 87612 KB Output is correct
12 Correct 205 ms 87672 KB Output is correct
13 Correct 205 ms 87928 KB Output is correct
14 Correct 214 ms 88184 KB Output is correct
15 Correct 205 ms 87932 KB Output is correct
16 Correct 219 ms 87672 KB Output is correct
17 Correct 205 ms 87524 KB Output is correct
18 Correct 214 ms 87544 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 80808 KB Output is correct
2 Correct 121 ms 1656 KB Output is correct
3 Correct 109 ms 1688 KB Output is correct
4 Correct 95 ms 1656 KB Output is correct
5 Correct 109 ms 1784 KB Output is correct
6 Correct 111 ms 1784 KB Output is correct
7 Correct 110 ms 1656 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 450 ms 81300 KB Output is correct
12 Correct 434 ms 81540 KB Output is correct
13 Correct 450 ms 81276 KB Output is correct
14 Correct 471 ms 81360 KB Output is correct
15 Correct 439 ms 81732 KB Output is correct
16 Correct 472 ms 81820 KB Output is correct
17 Correct 474 ms 81776 KB Output is correct
18 Correct 469 ms 81972 KB Output is correct
19 Correct 409 ms 81272 KB Output is correct
20 Correct 412 ms 81144 KB Output is correct
21 Correct 410 ms 81192 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 835 ms 81964 KB Output is correct
2 Incorrect 170 ms 3708 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 80808 KB Output is correct
2 Correct 121 ms 1656 KB Output is correct
3 Correct 109 ms 1688 KB Output is correct
4 Correct 95 ms 1656 KB Output is correct
5 Correct 109 ms 1784 KB Output is correct
6 Correct 111 ms 1784 KB Output is correct
7 Correct 110 ms 1656 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 450 ms 81300 KB Output is correct
12 Correct 434 ms 81540 KB Output is correct
13 Correct 450 ms 81276 KB Output is correct
14 Correct 471 ms 81360 KB Output is correct
15 Correct 439 ms 81732 KB Output is correct
16 Correct 472 ms 81820 KB Output is correct
17 Correct 474 ms 81776 KB Output is correct
18 Correct 469 ms 81972 KB Output is correct
19 Correct 409 ms 81272 KB Output is correct
20 Correct 412 ms 81144 KB Output is correct
21 Correct 410 ms 81192 KB Output is correct
22 Correct 1109 ms 80812 KB Output is correct
23 Correct 173 ms 1400 KB Output is correct
24 Correct 170 ms 1272 KB Output is correct
25 Correct 172 ms 1272 KB Output is correct
26 Correct 175 ms 1272 KB Output is correct
27 Correct 179 ms 1272 KB Output is correct
28 Correct 179 ms 1272 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 1124 ms 79748 KB Output is correct
33 Correct 1071 ms 79648 KB Output is correct
34 Correct 1251 ms 79736 KB Output is correct
35 Correct 1260 ms 79864 KB Output is correct
36 Correct 1000 ms 80012 KB Output is correct
37 Correct 1042 ms 79992 KB Output is correct
38 Correct 999 ms 79964 KB Output is correct
39 Correct 1263 ms 79840 KB Output is correct
40 Correct 1334 ms 79736 KB Output is correct
41 Correct 1271 ms 79736 KB Output is correct
42 Correct 1143 ms 79736 KB Output is correct
43 Correct 1069 ms 79724 KB Output is correct
44 Correct 1070 ms 79736 KB Output is correct
45 Correct 1065 ms 79736 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 81016 KB Output is correct
2 Correct 97 ms 3576 KB Output is correct
3 Correct 98 ms 3552 KB Output is correct
4 Correct 97 ms 3576 KB Output is correct
5 Correct 97 ms 3704 KB Output is correct
6 Correct 98 ms 3704 KB Output is correct
7 Correct 97 ms 3580 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 392 KB Output is correct
11 Correct 206 ms 87612 KB Output is correct
12 Correct 205 ms 87672 KB Output is correct
13 Correct 205 ms 87928 KB Output is correct
14 Correct 214 ms 88184 KB Output is correct
15 Correct 205 ms 87932 KB Output is correct
16 Correct 219 ms 87672 KB Output is correct
17 Correct 205 ms 87524 KB Output is correct
18 Correct 214 ms 87544 KB Output is correct
19 Correct 3 ms 640 KB Output is correct
20 Incorrect 1 ms 384 KB Output isn't correct
21 Halted 0 ms 0 KB -