제출 #1357584

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

jumps

#include <bits/stdc++.h>

using namespace std;

#define name "IO"
#define int long long

const int inf = 1e18 + 7;
const int maxn = 5e5 + 5;
const int mod = 1e9 + 7;
int n, q, a[maxn]; 

struct segTree
{
    struct Node 
    {
        int mxA = 0;
        int mx = -inf;
        int lazy = -inf;
    };

    int n; 
    vector<Node> st;

    segTree (int n_)
    {
        n = n_;
        st.resize(4 * n + 5);
    }

    void build(int id, int l, int r)
    {
        if(l == r)
        {
            st[id].mxA = a[l];
            return; 
        }
        int mid = l + r >> 1;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
        st[id].mxA = max(st[id * 2].mxA, st[id * 2 + 1].mxA);
    }

    void apply(int id, int val)
    {
        st[id].mx = max(st[id].mx, st[id].mxA + val);
        st[id].lazy = max(st[id].lazy, val);
    }
    
    void push(int id)
    {
        if(st[id].lazy == -inf) return;
        apply(id * 2, st[id].lazy);
        apply(id * 2 + 1, st[id].lazy);
        st[id].lazy = -inf;
    }

    void update(int id, int l, int r, int u, int v, int val)
    {
        if(l > v || r < u) return;
        if(l >= u && r <= v)
        {
            apply(id, val);
            return;
        }

        push(id);
        int mid = l + r >> 1;
        update(id * 2, l, mid, u, v, val);
        update(id * 2 + 1, mid + 1, r, u, v, val);
        st[id].mx = max(st[id * 2].mx, st[id * 2 + 1].mx);
    }

    int query(int id, int l, int r, int u, int v)
    {
        if(l > v || r < u) return -inf;
        if(l >= u && r <= v) return st[id].mx;

        push(id);
        int mid = l + r >> 1;
        return max(query(id * 2, l, mid, u, v), query(id * 2 + 1, mid + 1, r, u, v));
    }

    void update(int l, int r, int val)
    {
        if(l > r) return;
        update(1, 1, n, l, r, val);
    }

    int query(int l, int r)
    {
        if(l > r) return -inf;
        return query(1, 1, n, l, r);
    }

};

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

    cin >> q;
    vector<vector<pair<int, int>>> ask(n + 2); 
    for(int i = 1; i <= q; i++)
    {
        int l, r;
        cin >> l >> r; 
        ask[l].push_back({r, i});
    }

    vector<vector<int>> cand(n + 2);
    deque<int> st;

    for(int i = n; i >= 1; i--)
    {
        for(int j : st)
        {
            cand[i].push_back(j);
            if(a[j] >= a[i]) break;
        }

        while(!st.empty() && a[st.front()] <= a[i]) st.pop_front();
        st.push_front(i);
    }

    segTree seg(n);
    seg.build(1, 1, n);
    vector<int> ans(q + 1, 0);

    for(int l = n; l >= 1; l--)
    {
        for(int j : cand[l])
        {
            int stc = 2 * j - l;
            if(stc <= n)
            {
                seg.update(stc, n, a[l] + a[j]);
            }
        }

        for(auto [r, id] : ask[l])
        {
            ans[id] = seg.query(1, r);
        }
    }

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

signed main()
{
    if(fopen(name".INP","r"))
    {
        freopen(name".INP","r",stdin);
        // freopen(name".OUT","w",stdout);
    }


    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    clock_t start = clock();

    int t = 1;

    while(t--) solve();

    std::cerr << "Time: " << clock() - start << "ms\n";

    return 0;
}

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

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

• 서브태스크 1: 5 / 5
• 서브태스크 2: 14 / 14
• 서브태스크 3: 27 / 27
• 서브태스크 4: 54 / 54