oj.uz

Submission #815656

# Submission time Handle Problem Language Result Execution time Memory
815656 2023-08-08T17:48:45 Z MilosMilutinovic Fish 2 (JOI22_fish2) C++14
8 / 100
 4000 ms 249324 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);
    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;
  }
};

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 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);
  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:145:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  145 |     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 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 10 ms 1428 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 34924 KB Output is correct
3 Correct 85 ms 34556 KB Output is correct
4 Correct 87 ms 34916 KB Output is correct
5 Correct 86 ms 34752 KB Output is correct
6 Correct 58 ms 32036 KB Output is correct
7 Correct 45 ms 31196 KB Output is correct
8 Correct 57 ms 32024 KB Output is correct
9 Correct 46 ms 31276 KB Output is correct
10 Correct 84 ms 34520 KB Output is correct
11 Correct 88 ms 33840 KB Output is correct
12 Correct 52 ms 31904 KB Output is correct
13 Correct 52 ms 31824 KB Output is correct
14 Correct 71 ms 33108 KB Output is correct
15 Correct 76 ms 32976 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 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 10 ms 1428 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 34924 KB Output is correct
3 Correct 85 ms 34556 KB Output is correct
4 Correct 87 ms 34916 KB Output is correct
5 Correct 86 ms 34752 KB Output is correct
6 Correct 58 ms 32036 KB Output is correct
7 Correct 45 ms 31196 KB Output is correct
8 Correct 57 ms 32024 KB Output is correct
9 Correct 46 ms 31276 KB Output is correct
10 Correct 84 ms 34520 KB Output is correct
11 Correct 88 ms 33840 KB Output is correct
12 Correct 52 ms 31904 KB Output is correct
13 Correct 52 ms 31824 KB Output is correct
14 Correct 71 ms 33108 KB Output is correct
15 Correct 76 ms 32976 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Execution timed out 4078 ms 230572 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 34924 KB Output is correct
3 Correct 85 ms 34556 KB Output is correct
4 Correct 87 ms 34916 KB Output is correct
5 Correct 86 ms 34752 KB Output is correct
6 Correct 58 ms 32036 KB Output is correct
7 Correct 45 ms 31196 KB Output is correct
8 Correct 57 ms 32024 KB Output is correct
9 Correct 46 ms 31276 KB Output is correct
10 Correct 84 ms 34520 KB Output is correct
11 Correct 88 ms 33840 KB Output is correct
12 Correct 52 ms 31904 KB Output is correct
13 Correct 52 ms 31824 KB Output is correct
14 Correct 71 ms 33108 KB Output is correct
15 Correct 76 ms 32976 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Execution timed out 4093 ms 249324 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 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 10 ms 1428 KB Output isn't correct
6 Halted 0 ms 0 KB -