oj.uz

Submission #815642

# Submission time Handle Problem Language Result Execution time Memory
815642 2023-08-08T17:39:54 Z MilosMilutinovic Fish 2 (JOI22_fish2) C++14
8 / 100
 4000 ms 249276 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, 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(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 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 212 KB Output is correct
5 Incorrect 13 ms 1376 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 212 KB Output is correct
2 Correct 83 ms 34952 KB Output is correct
3 Correct 90 ms 34576 KB Output is correct
4 Correct 84 ms 34876 KB Output is correct
5 Correct 91 ms 34716 KB Output is correct
6 Correct 57 ms 32036 KB Output is correct
7 Correct 46 ms 31200 KB Output is correct
8 Correct 56 ms 32032 KB Output is correct
9 Correct 46 ms 31212 KB Output is correct
10 Correct 89 ms 34528 KB Output is correct
11 Correct 83 ms 33880 KB Output is correct
12 Correct 62 ms 31860 KB Output is correct
13 Correct 54 ms 31848 KB Output is correct
14 Correct 88 ms 33164 KB Output is correct
15 Correct 72 ms 32988 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 212 KB Output is correct
5 Incorrect 13 ms 1376 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 212 KB Output is correct
2 Correct 83 ms 34952 KB Output is correct
3 Correct 90 ms 34576 KB Output is correct
4 Correct 84 ms 34876 KB Output is correct
5 Correct 91 ms 34716 KB Output is correct
6 Correct 57 ms 32036 KB Output is correct
7 Correct 46 ms 31200 KB Output is correct
8 Correct 56 ms 32032 KB Output is correct
9 Correct 46 ms 31212 KB Output is correct
10 Correct 89 ms 34528 KB Output is correct
11 Correct 83 ms 33880 KB Output is correct
12 Correct 62 ms 31860 KB Output is correct
13 Correct 54 ms 31848 KB Output is correct
14 Correct 88 ms 33164 KB Output is correct
15 Correct 72 ms 32988 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Execution timed out 4058 ms 222272 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 212 KB Output is correct
2 Correct 83 ms 34952 KB Output is correct
3 Correct 90 ms 34576 KB Output is correct
4 Correct 84 ms 34876 KB Output is correct
5 Correct 91 ms 34716 KB Output is correct
6 Correct 57 ms 32036 KB Output is correct
7 Correct 46 ms 31200 KB Output is correct
8 Correct 56 ms 32032 KB Output is correct
9 Correct 46 ms 31212 KB Output is correct
10 Correct 89 ms 34528 KB Output is correct
11 Correct 83 ms 33880 KB Output is correct
12 Correct 62 ms 31860 KB Output is correct
13 Correct 54 ms 31848 KB Output is correct
14 Correct 88 ms 33164 KB Output is correct
15 Correct 72 ms 32988 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Execution timed out 4073 ms 249276 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 212 KB Output is correct
5 Incorrect 13 ms 1376 KB Output isn't correct
6 Halted 0 ms 0 KB -