oj.uz

Submission #270636

# Submission time Handle Problem Language Result Execution time Memory
270636 2020-08-17T20:33:32 Z Haunted_Cpp Progression (NOI20_progression) C++17
48 / 100
 1066 ms 70008 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 delta_pre, delta_suf;
    int t;
    Node() {
      pre = suf = best = 0;
      delta_pre = delta_suf = 0;
      t = 0;
      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;
      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;
      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 == INVALID) return;
    seg[node].delta_pre += seg[node].lazy;
    seg[node].delta_suf += 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 = 0;
  }
  
  void range_update(int ql, int qr, long long delta, int l, int r, int node) {
    push(l, r, node);
    if (l > qr || r < ql) return;
    if (l >= ql && r <= qr) {
      seg[node].lazy = delta;
      push(l, r, node);
      return;
    }
    const int mid = l + (r - l) / 2;
    range_update(ql, qr, delta, l, mid, 2 * node + 1);
    range_update(ql, qr, delta, 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;
  }
  void range_update(int ql, int qr, long long delta) {
    if (ql > qr) return;
    range_update(ql, qr, delta, 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);
  while(q--) {
    int t, lo, hi;
    cin >> t >> lo >> hi;
    --lo; hi -= 2; 
    if (t == 1) {
      int delta, d;
      cin >> delta >> d;
      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) {
      
    } else {
      cout << seg.range_query(lo, hi) + 1 << '\n';
    }
  }
  return 0;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 15.0

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

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 61304 KB Output is correct
2 Correct 103 ms 1016 KB Output is correct
3 Correct 105 ms 1016 KB Output is correct
4 Correct 91 ms 1020 KB Output is correct
5 Correct 107 ms 1144 KB Output is correct
6 Correct 99 ms 1144 KB Output is correct
7 Correct 99 ms 1144 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 440 ms 61304 KB Output is correct
12 Correct 382 ms 61560 KB Output is correct
13 Correct 399 ms 61304 KB Output is correct
14 Correct 403 ms 61216 KB Output is correct
15 Correct 378 ms 61432 KB Output is correct
16 Correct 442 ms 61816 KB Output is correct
17 Correct 453 ms 61808 KB Output is correct
18 Correct 437 ms 62072 KB Output is correct
19 Correct 363 ms 61176 KB Output is correct
20 Correct 366 ms 61176 KB Output is correct
21 Correct 359 ms 61220 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 61304 KB Output is correct
2 Correct 103 ms 1016 KB Output is correct
3 Correct 105 ms 1016 KB Output is correct
4 Correct 91 ms 1020 KB Output is correct
5 Correct 107 ms 1144 KB Output is correct
6 Correct 99 ms 1144 KB Output is correct
7 Correct 99 ms 1144 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 440 ms 61304 KB Output is correct
12 Correct 382 ms 61560 KB Output is correct
13 Correct 399 ms 61304 KB Output is correct
14 Correct 403 ms 61216 KB Output is correct
15 Correct 378 ms 61432 KB Output is correct
16 Correct 442 ms 61816 KB Output is correct
17 Correct 453 ms 61808 KB Output is correct
18 Correct 437 ms 62072 KB Output is correct
19 Correct 363 ms 61176 KB Output is correct
20 Correct 366 ms 61176 KB Output is correct
21 Correct 359 ms 61220 KB Output is correct
22 Correct 933 ms 61304 KB Output is correct
23 Correct 168 ms 1016 KB Output is correct
24 Correct 175 ms 1144 KB Output is correct
25 Correct 168 ms 1016 KB Output is correct
26 Correct 172 ms 1016 KB Output is correct
27 Correct 171 ms 1016 KB Output is correct
28 Correct 176 ms 1016 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 288 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 972 ms 66824 KB Output is correct
33 Correct 915 ms 69500 KB Output is correct
34 Correct 964 ms 66936 KB Output is correct
35 Correct 966 ms 67064 KB Output is correct
36 Correct 800 ms 66552 KB Output is correct
37 Correct 808 ms 66628 KB Output is correct
38 Correct 818 ms 66808 KB Output is correct
39 Correct 972 ms 69752 KB Output is correct
40 Correct 1066 ms 69880 KB Output is correct
41 Correct 1020 ms 69776 KB Output is correct
42 Correct 989 ms 69752 KB Output is correct
43 Correct 940 ms 70008 KB Output is correct
44 Correct 961 ms 69624 KB Output is correct
45 Correct 909 ms 69500 KB Output is correct

Subtask #6
0 / 17.0

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