제출 #1171218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171218		InvMOD	3단 점프 (JOI19_jumps)	C++20	100 / 100	768 ms	89616 KiB

jumps

#include<bits/stdc++.h>

using namespace std;

#define sz(v) (int)(v).size()

template<typename T> bool ckmx(T& a, const T& b){
    if(a < b)
        return a = b, true;
    return false;
}

using ll = long long;

struct SMT{
    struct Node{
        ll ab, c, best;
        Node(ll ab = 0, ll c = 0, ll best = 0): ab(ab), c(c), best(best) {}

        friend Node operator + (const Node& x, const Node& y){
            Node ans = Node();
            ans.ab = max(x.ab, y.ab);
            ans.c = max(x.c, y.c);
            ans.best = max({x.best, y.best, x.ab + y.c});
            return ans;
        }
    };

    int trsz;
    vector<Node> st;

    SMT(int n = 0): trsz(n), st((n << 2 | 1)) {}

    void apply(int id, ll val, int t){
        if(!t) ckmx(st[id].ab, val);
        else ckmx(st[id].c, val);

        st[id].best = st[id].ab + st[id].c;
    }

    void update(int id, int l, int r, int x, ll val, int t){
        if(l == r){
            apply(id, val, t);
        }
        else{
            int m = l+r>>1;
            if(x <= m)
                update(id << 1, l, m, x, val, t);
            else update(id << 1|1, m+1, r, x, val, t);

            st[id] = st[id << 1] + st[id << 1|1];
        }
    }

    Node get(int id, int l, int r, int u, int v){
        if(l >= u && r <= v) return st[id];

        int m = l+r>>1;
        return (u <= m ? get(id << 1, l, m, u, v) : Node()) +
                (v > m ? get(id << 1|1, m+1, r, u, v) : Node());
    }

    ll query(int l, int r){
        return get(1, 1, trsz, l, r).best;
    }

    void update(int x, ll val, int t){
        if(x > trsz) return;
        update(1, 1, trsz, x, val, t);
    }
};

const int N = 5e5 + 5;


void solve()
{
    int n; cin >> n;

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

    int q; cin >> q;

    vector<pair<int,int>> Q(q + 1);
    for(int i = 1; i <= q; i++){
        cin >> Q[i].first >> Q[i].second;
    }

    vector<vector<int>> saveQ(n + 1, vector<int>());
    for(int i = 1; i <= q; i++){
        saveQ[Q[i].first].push_back(i);
    }

    SMT st(n); stack<int> candidate;

    auto update_candidate = [&](int i, int j) -> void{
        ll value = 1ll * a[i] + 1ll * a[j];
        // (j - i) <= (k - j) -> k >= j + (j - i)
        int k = j + (j - i);
        st.update(k, value, 0);
    };

    vector<ll> answer(q + 1);

    /*
        if a[i] < a[st.top()] it's just useless to update it more
        (a[st.top()] with a[st.top() - 1] can give better answer) (more jumping range, more firmness)
        it can only contribute to position that i -> st.top() can contribute
    */

    for(int i = n; i >= 1; i--){
        st.update(i, a[i], 1);
        while(!candidate.empty() && a[i] >= a[candidate.top()]){
            update_candidate(i, candidate.top());
            candidate.pop();
        }

        if(!candidate.empty()){
            update_candidate(i, candidate.top());
        }
        candidate.push(i);

        for(int id : saveQ[i]){
            int r = Q[id].second;
            answer[id] = st.query(i, r);
        }
    }

    for(int i = 1; i <= q; i++){
        cout << answer[i] << "\n";
    }
}

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

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    solve();
    return 0;
}

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

jumps.cpp: In function 'int32_t main()':
jumps.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54