제출 #1112814

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1112814		Zero_OP	Fish 2 (JOI22_fish2)	C++14	5 / 100	4085 ms	2412 KiB

fish2

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 12
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17