제출 #679063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
679063		Cross_Ratio	3단 점프 (JOI19_jumps)	C++14	27 / 100	213 ms	33192 KiB

jumps

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct SegTree {
    struct Node {
        int v;
        int lz, ma;
        Node(int _v, int _l, int _m) : v(_v), lz(_l), ma(_m){}
        Node() : v(0), lz(0), ma(0) {}
    };
    vector<Node> seg;
    int MAX;
    SegTree(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
    }
    void cons() {
        for(int i = MAX/2-1;i>=1;i--) {
            seg[i].ma = max(seg[2*i].ma, seg[2*i+1].ma);
        }
    }
    void prop(int n, int ns, int ne) {
        if(seg[n].lz!=0) {
            seg[n].v = max(seg[n].v, seg[n].lz + seg[n].ma);
            if(n<MAX/2) {
                seg[2*n].lz = max(seg[2*n].lz, seg[n].lz);
                seg[2*n+1].lz = max(seg[2*n+1].lz, seg[n].lz);
            }
            seg[n].lz = 0;
        }
    }
    void add(int s, int e, int k, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return;
        if(s<=ns&&ne<=e) {
            seg[n].lz = max(seg[n].lz, k);
            prop(n,ns,ne);
            return;
        }
        int mid = ns + ne >> 1;
        add(s, e, k, 2*n, ns, mid);
        add(s, e, k, 2*n+1, mid, ne);
        if(n<MAX/2) seg[n].v = max(seg[2*n].v, seg[2*n+1].v);
    }
    int sum(int s, int e, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return 0;
        if(s<=ns&&ne<=e) return seg[n].v;
        int mid = ns + ne >> 1;
        return max(sum(s, e, 2*n, ns, mid), sum(s, e, 2*n+1, mid, ne));
    }
};
int A[500005];
int L[500005];
int R[500005];
int ans[500005];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;
    int i, j;
    for(i=0;i<N;i++) cin >> A[i];
    vector<int> V;
    vector<vector<int>> Q1, Q2;
    Q1.resize(N), Q2.resize(N);
    for(i=0;i<N;i++) {
        while(V.size()&&A[V.back()]<=A[i]) {
            Q1[V.back()].push_back(i);
            V.pop_back();
        }
        if(V.size()) Q1[V.back()].push_back(i);
        V.push_back(i);
    }
    int Q;
    cin >> Q;
    for(i=0;i<Q;i++) {
        cin >> L[i] >> R[i];
        L[i]--, R[i]--;
        Q2[L[i]].push_back(i);
    }
    SegTree tree(N+5);
    int MAX = tree.MAX;
    for(i=0;i<N;i++) {
        tree.seg[i+MAX/2].ma = A[i];
    }
    tree.cons();
    for(i=N-1;i>=0;i--) {
        for(int k : Q1[i]) {
            if(2*k-i<N) {
                tree.add(2*k-i, N, A[i] + A[k], 1, 0, MAX/2);
            }
        }
        for(int v : Q2[i]) {
            ans[v] = tree.sum(L[i]+2, R[i]+1, 1, 0, MAX/2);
        }
    }
    for(i=0;i<Q;i++) cout << ans[i] << '\n';
}

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

jumps.cpp: In member function 'void SegTree::add(long long int, long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:42:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
jumps.cpp: In member function 'long long int SegTree::sum(long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:51:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
jumps.cpp: In function 'int main()':
jumps.cpp:65:12: warning: unused variable 'j' [-Wunused-variable]
   65 |     int i, j;
      |            ^

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