oj.uz

Submission #270615

# Submission time Handle Problem Language Result Execution time Memory
270615 2020-08-17T19:58:26 Z Haunted_Cpp Progression (NOI20_progression) C++17
35 / 100
 479 ms 59128 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

class SegmentTree {
private:
  struct Node {
    int pre, suf, best;
    long long delta_pre, delta_suf;
    int t;
    Node() {
      pre = suf = best = 0;
      delta_pre = delta_suf = 0;
      t = 0;
    }
    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) {
    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;
  }
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;
  }
};
 
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;
    if (n == 1) {
      cout << 1 << '\n';
      continue;
    }
    if (t == 1) {
      
    } else if (t == 2) {
      
    } else {
      --hi;
      cout << seg.range_query(lo, hi) + 1 << '\n';
    }
  }
  return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 181 ms 51448 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 332 ms 51980 KB Output is correct
2 Correct 98 ms 1016 KB Output is correct
3 Correct 101 ms 1016 KB Output is correct
4 Correct 92 ms 888 KB Output is correct
5 Correct 95 ms 1016 KB Output is correct
6 Correct 108 ms 1016 KB Output is correct
7 Correct 96 ms 1016 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 479 ms 56568 KB Output is correct
12 Correct 333 ms 58104 KB Output is correct
13 Correct 357 ms 56696 KB Output is correct
14 Correct 359 ms 56696 KB Output is correct
15 Correct 335 ms 57976 KB Output is correct
16 Correct 367 ms 58616 KB Output is correct
17 Correct 357 ms 58548 KB Output is correct
18 Correct 399 ms 58616 KB Output is correct
19 Correct 301 ms 57848 KB Output is correct
20 Correct 302 ms 57848 KB Output is correct
21 Correct 300 ms 57848 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 51980 KB Output is correct
2 Correct 98 ms 1016 KB Output is correct
3 Correct 101 ms 1016 KB Output is correct
4 Correct 92 ms 888 KB Output is correct
5 Correct 95 ms 1016 KB Output is correct
6 Correct 108 ms 1016 KB Output is correct
7 Correct 96 ms 1016 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 479 ms 56568 KB Output is correct
12 Correct 333 ms 58104 KB Output is correct
13 Correct 357 ms 56696 KB Output is correct
14 Correct 359 ms 56696 KB Output is correct
15 Correct 335 ms 57976 KB Output is correct
16 Correct 367 ms 58616 KB Output is correct
17 Correct 357 ms 58548 KB Output is correct
18 Correct 399 ms 58616 KB Output is correct
19 Correct 301 ms 57848 KB Output is correct
20 Correct 302 ms 57848 KB Output is correct
21 Correct 300 ms 57848 KB Output is correct
22 Incorrect 305 ms 59128 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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