oj.uz

Submission #815633

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

using namespace std;

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) {
    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);
      return;      
    }
    push(x);
    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) {
      return {(int) 1e9, 0};
    }
    if (ll <= l && r <= rr) {
      return st[x];
    }
    int mid = l + r >> 1;
    return comb(query(2 * x, l, mid, ll, rr), query(2 * x + 1, mid + 1, r, ll, rr));
  }
  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);
    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;
  }
};

int 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]);
  }
  auto GetSum = [&](int L, int R) {
    return fenw.get(R) - fenw.get(L - 1);
  };
  const int inf = (int) 1e9;
  auto Valid = [&](int L, int R) {
    if (L + 1 >= R) {
      return false;
    }
    return min((L < 0 ? inf : a[L]), (R >= n ? inf : a[R])) > 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);
  auto Build = [&]() {
    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);
        }
      }
      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);
        }
      }
      stk.push_back(i);
    }
  };
  int q;
  cin >> q;
  while (q--) {
    int op;
    cin >> op;
    if (op == 1) {
      int x, y;
      cin >> x >> y;
      --x;
      fenw.modify(x, y - a[x]);
      a[x] = y;    
    } else {
      Build();
      int l, r;
      cin >> l >> r;
      --l; --r;
      {
        int L = l;
        for (int i = l + 1; i <= r; i++) {
          if (GetSum(L, i - 1) < a[i]) {
            l = i;
          }
        }
      }
      {
        int R = r;
        for (int i = r - 1; i >= l; i--) {
          if (GetSum(i + 1, R) < a[i]) {
            r = i;
          }
        }
      }
      //cout << l << " " << r << '\n';
      cout << mncnt::get(l, r) << '\n';
    }
  }
  return 0;
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 16 ms 1364 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 1 ms 212 KB Output is correct
2 Correct 82 ms 35428 KB Output is correct
3 Correct 78 ms 34620 KB Output is correct
4 Correct 85 ms 35488 KB Output is correct
5 Correct 81 ms 34728 KB Output is correct
6 Correct 73 ms 33116 KB Output is correct
7 Correct 58 ms 31440 KB Output is correct
8 Correct 73 ms 33076 KB Output is correct
9 Correct 59 ms 31428 KB Output is correct
10 Correct 84 ms 33504 KB Output is correct
11 Correct 68 ms 33016 KB Output is correct
12 Correct 69 ms 32172 KB Output is correct
13 Correct 60 ms 32120 KB Output is correct
14 Correct 91 ms 33616 KB Output is correct
15 Correct 65 ms 33516 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 82 ms 35428 KB Output is correct
3 Correct 78 ms 34620 KB Output is correct
4 Correct 85 ms 35488 KB Output is correct
5 Correct 81 ms 34728 KB Output is correct
6 Correct 73 ms 33116 KB Output is correct
7 Correct 58 ms 31440 KB Output is correct
8 Correct 73 ms 33076 KB Output is correct
9 Correct 59 ms 31428 KB Output is correct
10 Correct 84 ms 33504 KB Output is correct
11 Correct 68 ms 33016 KB Output is correct
12 Correct 69 ms 32172 KB Output is correct
13 Correct 60 ms 32120 KB Output is correct
14 Correct 91 ms 33616 KB Output is correct
15 Correct 65 ms 33516 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Execution timed out 4032 ms 207464 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 82 ms 35428 KB Output is correct
3 Correct 78 ms 34620 KB Output is correct
4 Correct 85 ms 35488 KB Output is correct
5 Correct 81 ms 34728 KB Output is correct
6 Correct 73 ms 33116 KB Output is correct
7 Correct 58 ms 31440 KB Output is correct
8 Correct 73 ms 33076 KB Output is correct
9 Correct 59 ms 31428 KB Output is correct
10 Correct 84 ms 33504 KB Output is correct
11 Correct 68 ms 33016 KB Output is correct
12 Correct 69 ms 32172 KB Output is correct
13 Correct 60 ms 32120 KB Output is correct
14 Correct 91 ms 33616 KB Output is correct
15 Correct 65 ms 33516 KB Output is correct
16 Correct 0 ms 320 KB Output is correct
17 Execution timed out 4107 ms 244096 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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