oj.uz

Submission #1112814

# Submission time Handle Problem Language Result Execution time Memory
1112814 2024-11-15T01:17:44 Z Zero_OP Fish 2 (JOI22_fish2) C++14
5 / 100
 4000 ms 2412 KB 
#include <bits/stdc++.h>

using namespace std;

template<typename T>
struct segment_tree{
    vector<T> st;
    int n;

    segment_tree(int n) : n(n), st(n * 2 + 1) {}

    void update(int i, T v){
        st[i += n] = v;
        for(; i > 1; i >>= 1){
            st[i >> 1] = max(st[i], st[i ^ 1]);
        }
    }

    T query(int l, int r){
         l += n;
         r += n + 1;
         T res = {0, 0};

         for(; l < r; l >>= 1, r >>= 1){
            if(l & 1) res = max(res, st[l++]);
            if(r & 1) res = max(res, st[--r]);
         }
         return res;
    }
};

template<typename T>
struct fenwick_tree{
    vector<T> bit;
    static constexpr int offset = 1;
    fenwick_tree(int n) : bit(n + 1, 0) {}

    void update(int id, T val){
        id += offset;
        for(; id < (int)bit.size(); id += id & (-id)){
            bit[id] += val;
        }
    }

    T query(int l, int r){
        T res(0);
        for(; l > 0; l -= l & (-l)) res -= bit[l];
        for(++r; r > 0; r -= r & (-r)) res += bit[r];
        return res;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    if(fopen("task.inp", "r")){
        freopen("task.inp", "r", stdin);
    }

    int N;
    cin >> N;
    vector<int> a(N + 2);
    for(int i = 1; i <= N; ++i){
        cin >> a[i];
    }

    const long long inf = 1e18;
    int Q;
    cin >> Q;
    while(Q--){
        int type;
        cin >> type;
        if(type == 1){
            int i, v;
            cin >> i >> v;
            a[i] = v;
        } else{
            int lq, rq;
            cin >> lq >> rq;

            vector<pair<int, int>> bad_intervals;

            vector<long long> pref(N + 1);
            for(int i = 1; i <= N; ++i) pref[i] = pref[i - 1] + a[i];

            for(int l = lq; l <= rq; ++l){
                for(int r = l; r <= rq; ++r){
                    if(l == lq && r == rq) continue;
                    long long target = min((l == lq ? inf : a[l - 1]), (r == rq ? inf : a[r + 1]));
                    if(pref[r] - pref[l - 1] < target) {
                        bad_intervals.emplace_back(l, r);
                    }
                }
            }

            assert((int)bad_intervals.size() <= N);
            vector<int> diff(N + 1);

            for(auto [l, r] : bad_intervals) {
                ++diff[l];
                if(r < N) --diff[r + 1]; 
            }

            int cnt = 0;
            for(int i = 1; i <= N; ++i){
                diff[i] += diff[i - 1];
                if(lq <= i && i <= rq && diff[i] == 0){
                    ++cnt;
                }
            }

            cout << cnt << '\n';
        }
    }

    return 0;
}

Compilation message

fish2.cpp: In function 'int main()':
fish2.cpp:100:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  100 |             for(auto [l, r] : bad_intervals) {
      |                      ^
fish2.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 11 ms 336 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 13 ms 336 KB Output is correct
9 Correct 23 ms 336 KB Output is correct
10 Correct 7 ms 336 KB Output is correct
11 Correct 17 ms 336 KB Output is correct
12 Correct 5 ms 336 KB Output is correct
13 Correct 17 ms 336 KB Output is correct
14 Correct 5 ms 336 KB Output is correct
15 Correct 10 ms 336 KB Output is correct
16 Correct 23 ms 336 KB Output is correct
17 Correct 8 ms 336 KB Output is correct
18 Correct 17 ms 336 KB Output is correct
19 Correct 8 ms 492 KB Output is correct
20 Correct 69 ms 336 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Execution timed out 4085 ms 2412 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 11 ms 336 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 13 ms 336 KB Output is correct
9 Correct 23 ms 336 KB Output is correct
10 Correct 7 ms 336 KB Output is correct
11 Correct 17 ms 336 KB Output is correct
12 Correct 5 ms 336 KB Output is correct
13 Correct 17 ms 336 KB Output is correct
14 Correct 5 ms 336 KB Output is correct
15 Correct 10 ms 336 KB Output is correct
16 Correct 23 ms 336 KB Output is correct
17 Correct 8 ms 336 KB Output is correct
18 Correct 17 ms 336 KB Output is correct
19 Correct 8 ms 492 KB Output is correct
20 Correct 69 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Execution timed out 4085 ms 2412 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Execution timed out 4085 ms 2412 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Execution timed out 4085 ms 2412 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 11 ms 336 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 13 ms 336 KB Output is correct
9 Correct 23 ms 336 KB Output is correct
10 Correct 7 ms 336 KB Output is correct
11 Correct 17 ms 336 KB Output is correct
12 Correct 5 ms 336 KB Output is correct
13 Correct 17 ms 336 KB Output is correct
14 Correct 5 ms 336 KB Output is correct
15 Correct 10 ms 336 KB Output is correct
16 Correct 23 ms 336 KB Output is correct
17 Correct 8 ms 336 KB Output is correct
18 Correct 17 ms 336 KB Output is correct
19 Correct 8 ms 492 KB Output is correct
20 Correct 69 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Execution timed out 4085 ms 2412 KB Time limit exceeded
23 Halted 0 ms 0 KB -