oj.uz

Submission #270626

# Submission time Handle Problem Language Result Execution time Memory
270626 2020-08-17T20:28:12 Z Haunted_Cpp Progression (NOI20_progression) C++17
35 / 100
 978 ms 62984 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) {
    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];
  }
  SegmentTree seg(diff);
  while(q--) {
    int t, lo, hi;
    cin >> t >> lo >> hi;
    --lo; hi -= 2;
    if (n == 1) {
      cout << 1 << '\n';
      continue;
    }
    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 275 ms 62332 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 376 ms 61348 KB Output is correct
2 Correct 100 ms 888 KB Output is correct
3 Correct 97 ms 888 KB Output is correct
4 Correct 91 ms 888 KB Output is correct
5 Correct 101 ms 1016 KB Output is correct
6 Correct 102 ms 1020 KB Output is correct
7 Correct 100 ms 1268 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 387 ms 61944 KB Output is correct
12 Correct 384 ms 62196 KB Output is correct
13 Correct 393 ms 62072 KB Output is correct
14 Correct 379 ms 61944 KB Output is correct
15 Correct 367 ms 62200 KB Output is correct
16 Correct 383 ms 62584 KB Output is correct
17 Correct 390 ms 62584 KB Output is correct
18 Correct 384 ms 62584 KB Output is correct
19 Correct 351 ms 61944 KB Output is correct
20 Correct 343 ms 61816 KB Output is correct
21 Correct 345 ms 61816 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 61348 KB Output is correct
2 Correct 100 ms 888 KB Output is correct
3 Correct 97 ms 888 KB Output is correct
4 Correct 91 ms 888 KB Output is correct
5 Correct 101 ms 1016 KB Output is correct
6 Correct 102 ms 1020 KB Output is correct
7 Correct 100 ms 1268 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 387 ms 61944 KB Output is correct
12 Correct 384 ms 62196 KB Output is correct
13 Correct 393 ms 62072 KB Output is correct
14 Correct 379 ms 61944 KB Output is correct
15 Correct 367 ms 62200 KB Output is correct
16 Correct 383 ms 62584 KB Output is correct
17 Correct 390 ms 62584 KB Output is correct
18 Correct 384 ms 62584 KB Output is correct
19 Correct 351 ms 61944 KB Output is correct
20 Correct 343 ms 61816 KB Output is correct
21 Correct 345 ms 61816 KB Output is correct
22 Correct 978 ms 62984 KB Output is correct
23 Correct 186 ms 3576 KB Output is correct
24 Correct 176 ms 3636 KB Output is correct
25 Correct 176 ms 3576 KB Output is correct
26 Correct 206 ms 3580 KB Output is correct
27 Correct 199 ms 3708 KB Output is correct
28 Correct 183 ms 3640 KB Output is correct
29 Incorrect 1 ms 384 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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