oj.uz

Submission #817796

# Submission time Handle Problem Language Result Execution time Memory
817796 2023-08-09T16:28:28 Z MilosMilutinovic Fish 2 (JOI22_fish2) C++14
8 / 100
 4000 ms 40432 KB 
/**
 *    author:  wxhtzdy
 *    created: 07.08.2023 10:57:57
**/
#include <bits/stdc++.h>

using namespace std;

#define int long long

namespace mncnt {
  struct node {
    int mn;
    int cnt;
  };
  node comb(node l, node r) {
    node res;
    res.mn = min(l.mn, r.mn);
    res.cnt = (l.mn == res.mn ? l.cnt : 0) + (r.mn == res.mn ? r.cnt : 0);
    return res;
  }
  vector<node> st;
  vector<int> lzy;
  int n;
  void init(int _n) {
    n = _n;
    st.resize(8 * n);
    lzy.resize(8 * n);
  }
  void push(int x, int l, int r) {
    if (l != r) {
      st[2 * x].mn += lzy[x];
      st[2 * x + 1].mn += lzy[x];
      lzy[2 * x] += lzy[x];
      lzy[2 * x + 1] += lzy[x];
    }
    lzy[x] = 0;
  }
  void pull(int x) {
    st[x] = comb(st[2 * x], st[2 * x + 1]);
  }
  void build(int x, int l, int r) {
    lzy[x] = 0;
    if (l == r) {
      st[x].mn = 0;
      st[x].cnt = 1;
      return;
    }
    int mid = l + r >> 1;
    build(x * 2, l, mid);
    build(x * 2 + 1, mid + 1, r);
    pull(x);
  }
  void update(int x, int l, int r, int ll, int rr, int v) {
    if (l > r || l > rr || r < ll || ll > rr) {
      return;
    }
    if (ll <= l && r <= rr) {
      lzy[x] += v;
      st[x].mn += v;
      push(x, l, r);
      return;      
    }
    push(x, l, r);
    int mid = l + r >> 1;
    update(x * 2, l, mid, ll, rr, v);
    update(x * 2 + 1, mid + 1, r, ll, rr, v);
    pull(x);
  }
  node query(int x, int l, int r, int ll, int rr) {
    if (l > r || l > rr || r < ll || ll > rr) {
      node nd;
      nd.mn = 1000000000;
      nd.cnt = 0;
      return nd;
    }
    if (ll <= l && r <= rr) {
      return st[x];
    }
    push(x, l, r);
    int mid = l + r >> 1;
    node ndl = query(2 * x, l, mid, ll, rr);
    node ndr = query(2 * x + 1, mid + 1, r, ll, rr);
    pull(x);
    return comb(ndl, ndr);
  }
  void update(int l, int r, int v) {
    update(1, 0, n - 1, l, r, v);
  }
  int get(int l, int r) {
    if (l > r) {
      return 0;
    }
    node nd = query(1, 0, n - 1, l, r);
    assert(nd.mn >= 0);
    return nd.mn == 0 ? nd.cnt : 0;
  }
};

template <typename T>
class fenwick {
  public:
  vector<T> fenw;
  int n;
  fenwick(int _n) : n(_n) {
    fenw.resize(n);
  }
  void modify(int x, T v) {
    while (x < n) {
      fenw[x] += v;
      x |= (x + 1);
    }
  }
  T get(int x) {
    T v{};
    while (x >= 0) {
      v += fenw[x];
      x = (x & (x + 1)) - 1;
    }
    return v;
  }
};

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  fenwick<long long> fenw(n);
  for (int i = 0; i < n; i++) {
    fenw.modify(i, a[i]);
  }
  function<long long(int, int)> GetSum = [&](int L, int R) {
    return fenw.get(R) - fenw.get(L - 1);
  };
  const long long inf = (long long) 1e18;
  auto Valid = [&](int L, int R) {
    if (L + 1 >= R) {
      return false;
    }                                                   
    return min((L < 0 ? inf : a[L] * 1LL), (R >= n ? inf : a[R] * 1LL)) > GetSum(L + 1, R - 1);
  };
  vector<vector<pair<int, int>>> segs(8 * n);
  function<void(int, int, int, int, int, int, int)> Add = [&](int x, int l, int r, int ll, int rr, int vl, int vr) {
    if (l > r || l > rr || r < ll || ll > rr) {
      return;
    }
    if (ll <= l && r <= rr) {
      segs[x].emplace_back(vl, vr);
      return;
    }
    int mid = l + r >> 1;
    Add(x * 2, l, mid, ll, rr, vl, vr);
    Add(x * 2 + 1, mid + 1, r, ll, rr, vl, vr);
  };               
  mncnt::init(n);
  mncnt::build(1, 0, n - 1);
  auto Build = [&]() {
    for (int i = 0; i < n; i++) {
      fenw.fenw[i] = 0;
    }
    for (int i = 0; i < n; i++) {
      fenw.modify(i, a[i]);
    }
    mncnt::init(n);
    mncnt::build(1, 0, n - 1);
    vector<int> stk;
    for (int i = 0; i < n; i++) {
      while (!stk.empty() && a[stk.back()] <= a[i]) {
        if (Valid(stk.back(), i)) {
          // cout << "Bad seg " << stk.back() + 1 << " " << i - 1 << '\n';
          //Add(1, 0, n - 1, max(0, stk.back()), i, stk.back() + 1, i - 1);
          mncnt::update(stk.back() + 1, i - 1, 1);
        }
        stk.pop_back();
      }
      if (stk.empty()) {
        if (Valid(-1, i)) {
          // cout << "Bad seg " << 0 << " " << i - 1 << '\n';
          //Add(1, 0, n - 1, 0, i, 0, i - 1);
          mncnt::update(0, i - 1, 1);
        }
      } else if (Valid(stk.back(), i)) {
        mncnt::update(stk.back() + 1, i - 1, 1);
      }
      stk.push_back(i);
    }
    stk.clear();
    for (int i = n - 1; i >= 0; i--) {
      while (!stk.empty() && a[stk.back()] <= a[i]) {
        if (Valid(i, stk.back())) {
          // cout << "Bad seg " << i + 1 << " " << stk.back() - 1 << '\n';
          //Add(1, 0, n - 1, i, min(n - 1, stk.back()), i + 1, stk.back() - 1);  
          mncnt::update(i + 1, stk.back() - 1, 1);
        }
        stk.pop_back();
      }
      if (stk.empty()) {
        if (Valid(i, n)) {
          // cout << "Bad seg " << i + 1 << " " << stk.back() - 1 << '\n';
          //Add(1, 0, n - 1, i, n - 1, i + 1, n - 1);
          mncnt::update(i + 1, n - 1, 1);
        }
      } else if (Valid(i, stk.back())) {
        mncnt::update(i + 1, stk.back() - 1, 1);
      }
      stk.push_back(i);
    }
  };
  int q;
  cin >> q;
  while (q--) {
    int op;
    cin >> op;
    if (op == 1) {
      int x, y;
      cin >> x >> y;
      --x;
      a[x] = y;    
    } else {
      Build();
      int l, r;
      cin >> l >> r;
      --l; --r;
      int L = l, R = r;
      {
        for (int i = L + 1; i <= R; i++) {
          if (GetSum(L, i - 1) < a[i]) {
            l = i;
          }
        }
      }
      {
        for (int i = R - 1; i >= L; i--) {
          if (GetSum(i + 1, R) < a[i]) {
            r = i;
          }
        }
      }
      assert(l <= r);
      //cout << l << " " << r << '\n';
      cout << mncnt::get(l, r) << '\n';
    }
  }
  return 0;
}

Compilation message

fish2.cpp: In function 'void mncnt::build(long long int, long long int, long long int)':
fish2.cpp:49:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |     int mid = l + r >> 1;
      |               ~~^~~
fish2.cpp: In function 'void mncnt::update(long long int, long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |     int mid = l + r >> 1;
      |               ~~^~~
fish2.cpp: In function 'mncnt::node mncnt::query(long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:81:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |     int mid = l + r >> 1;
      |               ~~^~~
fish2.cpp: In lambda function:
fish2.cpp:156:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  156 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Incorrect 10 ms 452 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 316 KB Output is correct
2 Correct 68 ms 39976 KB Output is correct
3 Correct 67 ms 39796 KB Output is correct
4 Correct 72 ms 40048 KB Output is correct
5 Correct 74 ms 39804 KB Output is correct
6 Correct 54 ms 40404 KB Output is correct
7 Correct 43 ms 39600 KB Output is correct
8 Correct 54 ms 40432 KB Output is correct
9 Correct 43 ms 39584 KB Output is correct
10 Correct 53 ms 40048 KB Output is correct
11 Correct 54 ms 39764 KB Output is correct
12 Correct 49 ms 39636 KB Output is correct
13 Correct 50 ms 39712 KB Output is correct
14 Correct 59 ms 40068 KB Output is correct
15 Correct 62 ms 40064 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Incorrect 10 ms 452 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 316 KB Output is correct
2 Correct 68 ms 39976 KB Output is correct
3 Correct 67 ms 39796 KB Output is correct
4 Correct 72 ms 40048 KB Output is correct
5 Correct 74 ms 39804 KB Output is correct
6 Correct 54 ms 40404 KB Output is correct
7 Correct 43 ms 39600 KB Output is correct
8 Correct 54 ms 40432 KB Output is correct
9 Correct 43 ms 39584 KB Output is correct
10 Correct 53 ms 40048 KB Output is correct
11 Correct 54 ms 39764 KB Output is correct
12 Correct 49 ms 39636 KB Output is correct
13 Correct 50 ms 39712 KB Output is correct
14 Correct 59 ms 40068 KB Output is correct
15 Correct 62 ms 40064 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Execution timed out 4059 ms 39892 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 316 KB Output is correct
2 Correct 68 ms 39976 KB Output is correct
3 Correct 67 ms 39796 KB Output is correct
4 Correct 72 ms 40048 KB Output is correct
5 Correct 74 ms 39804 KB Output is correct
6 Correct 54 ms 40404 KB Output is correct
7 Correct 43 ms 39600 KB Output is correct
8 Correct 54 ms 40432 KB Output is correct
9 Correct 43 ms 39584 KB Output is correct
10 Correct 53 ms 40048 KB Output is correct
11 Correct 54 ms 39764 KB Output is correct
12 Correct 49 ms 39636 KB Output is correct
13 Correct 50 ms 39712 KB Output is correct
14 Correct 59 ms 40068 KB Output is correct
15 Correct 62 ms 40064 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Execution timed out 4062 ms 40168 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 320 KB Output is correct
5 Incorrect 10 ms 452 KB Output isn't correct
6 Halted 0 ms 0 KB -