제출 #678113

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
678113		qwerasdfzxcl	3단 점프 (JOI19_jumps)	C++17	100 / 100	948 ms	67856 KiB

jumps

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
int a[500500], L[500500], R[500500], ans[500500];
vector<int> V[500500];

struct Seg{
    int tree[1101000], tree2[1101000], lazy[1101000];
    void init(int i, int l, int r){
        lazy[i] = 0;
        if (l==r){
            tree[i] = tree2[i] = a[l];
            return;
        }
        int m = (l+r)>>1;
        init(i<<1, l, m); init(i<<1|1, m+1, r);
        tree[i] = max(tree[i<<1], tree[i<<1|1]);
        tree2[i] = max(tree2[i<<1], tree2[i<<1|1]);
    }
    void propagate(int i, int l, int r){
        tree[i] = max(tree[i], tree2[i] + lazy[i]);
        if (l!=r){
            lazy[i<<1] = max(lazy[i<<1], lazy[i]);
            lazy[i<<1|1] = max(lazy[i<<1|1], lazy[i]);
        }
        lazy[i] = 0;
    }
    void update(int i, int l, int r, int s, int e, int x){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i] = max(lazy[i], x);
            propagate(i, l, r);
            return;
        }

        int m = (l+r)>>1;
        update(i<<1, l, m, s, e, x);
        update(i<<1|1, m+1, r, s, e, x);
        tree[i] = max(tree[i<<1], tree[i<<1|1]);
    }
    int query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if (r<s || e<l) return 0;
        if (s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return max(query(i<<1, l, m, s, e), query(i<<1|1, m+1, r, s, e));
    }
}tree;

bool cmp(int i, int j){return L[i] > L[j];}

int main(){
    int n;
    scanf("%d", &n);
    for (int i=1;i<=n;i++) scanf("%d", a+i);

    vector<int> st;
    for (int i=1;i<=n;i++){
        while(!st.empty() && a[st.back()] <= a[i]){
            V[st.back()].push_back(i);
            st.pop_back();
        }
        if (!st.empty()) V[st.back()].push_back(i);
        st.push_back(i);
    }

    int q;
    vector<int> I;
    scanf("%d", &q);
    for (int i=1;i<=q;i++){
        scanf("%d %d", L+i, R+i);
        I.push_back(i);
    }

    sort(I.begin(), I.end(), cmp);
    tree.init(1, 1, n);

    int pt = n+1;
    for (auto &i:I){
        while(L[i] < pt){
            --pt;
            for (auto &r:V[pt]){
                tree.update(1, 1, n, r*2-pt, n, a[pt] + a[r]);
                //printf("update (%d %d): %d %d %d\n", pt, r, r*2-pt, n, a[pt] + a[r]);
                //if (pt==3 && r==4) printf("%d\n", tree.query(1, 1, n, 5, 5));
            }
        }

        //printf("pt = %d -> %d %d\n", pt, L[i], R[i]);

        ans[i] = tree.query(1, 1, n, L[i]+2, R[i]);
    }

    for (int i=1;i<=q;i++) printf("%d\n", ans[i]);
    return 0;
}

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

jumps.cpp: In function 'int main()':
jumps.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
jumps.cpp:57:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     for (int i=1;i<=n;i++) scanf("%d", a+i);
      |                            ~~~~~^~~~~~~~~~~
jumps.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
jumps.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         scanf("%d %d", L+i, R+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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