oj.uz

Submission #817805

# Submission time Handle Problem Language Result Execution time Memory
817805 2023-08-09T16:36:13 Z MilosMilutinovic Fish 2 (JOI22_fish2) C++14
13 / 100
 4000 ms 40020 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.cnt;
  }
};

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;
    }
    assert(L >= 0 || R < n);                                    
    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;
      if (l == r) {
        cout << 1 << '\n';
        continue;
      }
      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:157:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  157 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Correct 13 ms 516 KB Output is correct
6 Correct 49 ms 504 KB Output is correct
7 Correct 13 ms 520 KB Output is correct
8 Correct 44 ms 516 KB Output is correct
9 Correct 54 ms 588 KB Output is correct
10 Correct 14 ms 528 KB Output is correct
11 Correct 37 ms 528 KB Output is correct
12 Correct 12 ms 468 KB Output is correct
13 Correct 45 ms 508 KB Output is correct
14 Correct 8 ms 528 KB Output is correct
15 Correct 30 ms 468 KB Output is correct
16 Correct 30 ms 468 KB Output is correct
17 Correct 18 ms 468 KB Output is correct
18 Correct 45 ms 500 KB Output is correct
19 Correct 22 ms 528 KB Output is correct
20 Correct 49 ms 512 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 67 ms 39424 KB Output is correct
3 Correct 67 ms 39364 KB Output is correct
4 Correct 68 ms 39464 KB Output is correct
5 Correct 72 ms 39460 KB Output is correct
6 Correct 53 ms 39468 KB Output is correct
7 Correct 47 ms 39460 KB Output is correct
8 Correct 65 ms 39372 KB Output is correct
9 Correct 44 ms 39372 KB Output is correct
10 Correct 53 ms 39468 KB Output is correct
11 Correct 51 ms 39380 KB Output is correct
12 Correct 51 ms 39464 KB Output is correct
13 Correct 58 ms 39372 KB Output is correct
14 Correct 71 ms 39464 KB Output is correct
15 Correct 61 ms 39392 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 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 Correct 13 ms 516 KB Output is correct
6 Correct 49 ms 504 KB Output is correct
7 Correct 13 ms 520 KB Output is correct
8 Correct 44 ms 516 KB Output is correct
9 Correct 54 ms 588 KB Output is correct
10 Correct 14 ms 528 KB Output is correct
11 Correct 37 ms 528 KB Output is correct
12 Correct 12 ms 468 KB Output is correct
13 Correct 45 ms 508 KB Output is correct
14 Correct 8 ms 528 KB Output is correct
15 Correct 30 ms 468 KB Output is correct
16 Correct 30 ms 468 KB Output is correct
17 Correct 18 ms 468 KB Output is correct
18 Correct 45 ms 500 KB Output is correct
19 Correct 22 ms 528 KB Output is correct
20 Correct 49 ms 512 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 67 ms 39424 KB Output is correct
23 Correct 67 ms 39364 KB Output is correct
24 Correct 68 ms 39464 KB Output is correct
25 Correct 72 ms 39460 KB Output is correct
26 Correct 53 ms 39468 KB Output is correct
27 Correct 47 ms 39460 KB Output is correct
28 Correct 65 ms 39372 KB Output is correct
29 Correct 44 ms 39372 KB Output is correct
30 Correct 53 ms 39468 KB Output is correct
31 Correct 51 ms 39380 KB Output is correct
32 Correct 51 ms 39464 KB Output is correct
33 Correct 58 ms 39372 KB Output is correct
34 Correct 71 ms 39464 KB Output is correct
35 Correct 61 ms 39392 KB Output is correct
36 Execution timed out 4050 ms 40020 KB Time limit exceeded
37 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 67 ms 39424 KB Output is correct
3 Correct 67 ms 39364 KB Output is correct
4 Correct 68 ms 39464 KB Output is correct
5 Correct 72 ms 39460 KB Output is correct
6 Correct 53 ms 39468 KB Output is correct
7 Correct 47 ms 39460 KB Output is correct
8 Correct 65 ms 39372 KB Output is correct
9 Correct 44 ms 39372 KB Output is correct
10 Correct 53 ms 39468 KB Output is correct
11 Correct 51 ms 39380 KB Output is correct
12 Correct 51 ms 39464 KB Output is correct
13 Correct 58 ms 39372 KB Output is correct
14 Correct 71 ms 39464 KB Output is correct
15 Correct 61 ms 39392 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Execution timed out 4045 ms 39416 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 67 ms 39424 KB Output is correct
3 Correct 67 ms 39364 KB Output is correct
4 Correct 68 ms 39464 KB Output is correct
5 Correct 72 ms 39460 KB Output is correct
6 Correct 53 ms 39468 KB Output is correct
7 Correct 47 ms 39460 KB Output is correct
8 Correct 65 ms 39372 KB Output is correct
9 Correct 44 ms 39372 KB Output is correct
10 Correct 53 ms 39468 KB Output is correct
11 Correct 51 ms 39380 KB Output is correct
12 Correct 51 ms 39464 KB Output is correct
13 Correct 58 ms 39372 KB Output is correct
14 Correct 71 ms 39464 KB Output is correct
15 Correct 61 ms 39392 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Execution timed out 4041 ms 39412 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 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 Correct 13 ms 516 KB Output is correct
6 Correct 49 ms 504 KB Output is correct
7 Correct 13 ms 520 KB Output is correct
8 Correct 44 ms 516 KB Output is correct
9 Correct 54 ms 588 KB Output is correct
10 Correct 14 ms 528 KB Output is correct
11 Correct 37 ms 528 KB Output is correct
12 Correct 12 ms 468 KB Output is correct
13 Correct 45 ms 508 KB Output is correct
14 Correct 8 ms 528 KB Output is correct
15 Correct 30 ms 468 KB Output is correct
16 Correct 30 ms 468 KB Output is correct
17 Correct 18 ms 468 KB Output is correct
18 Correct 45 ms 500 KB Output is correct
19 Correct 22 ms 528 KB Output is correct
20 Correct 49 ms 512 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 67 ms 39424 KB Output is correct
23 Correct 67 ms 39364 KB Output is correct
24 Correct 68 ms 39464 KB Output is correct
25 Correct 72 ms 39460 KB Output is correct
26 Correct 53 ms 39468 KB Output is correct
27 Correct 47 ms 39460 KB Output is correct
28 Correct 65 ms 39372 KB Output is correct
29 Correct 44 ms 39372 KB Output is correct
30 Correct 53 ms 39468 KB Output is correct
31 Correct 51 ms 39380 KB Output is correct
32 Correct 51 ms 39464 KB Output is correct
33 Correct 58 ms 39372 KB Output is correct
34 Correct 71 ms 39464 KB Output is correct
35 Correct 61 ms 39392 KB Output is correct
36 Execution timed out 4050 ms 40020 KB Time limit exceeded
37 Halted 0 ms 0 KB -