제출 #749431

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

jumps

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
using namespace std;

const int N = 5e5 + 5;
int n, nq, a[N], t[4 * N], lazy[4 * N], mx[4 * N], f[4 * N], ans[N];
vector <int> opt[N];
vector <pair<int, ii> > q;
stack <int> st;

void build(int i, int l, int r) {
    if(l == r) {
        mx[i] = a[l];
        return ;
    }
    int mid = l + r >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
    mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
}

void down(int i) {
    if(!down[i]) return ;
    t[i << 1] = max(t[i << 1], lazy[i]);
    f[i << 1] = max(f[i << 1], t[i << 1] + mx[i << 1]);
    lazy[i << 1] = max(lazy[i << 1], lazy[i]);
    t[i << 1 | 1] = max(t[i << 1 | 1], lazy[i]);
    f[i << 1 | 1] = max(f[i << 1 | 1], t[i << 1 | 1] + mx[i << 1 | 1]);
    lazy[i << 1 | 1] = max(lazy[i << 1 | 1], lazy[i]);
    lazy[i] = 0;
}

void upd(int i, int l, int r, int u, int v, int val) {
    if(l > v || u > r) return ;
    if(u <= l && r <= v) {
        t[i] = max(t[i], val);
        lazy[i] = max(lazy[i], val);
        f[i] = max(f[i], t[i] + mx[i]);
        return ;
    }
    down(i);
    int mid = l + r >> 1;
    upd(i << 1, l, mid, u, v, val);
    upd(i << 1 | 1, mid + 1, r, u, v, val);
    f[i] = max(f[i << 1], f[i << 1 | 1]);
}

int get(int i, int l, int r, int u, int v) {
    if(l > v || u > r) return 0;
    if(u <= l && r <= v) return f[i];
    down(i);
    int mid = l + r >> 1;
    return max(get(i << 1, l, mid, u, v) , get(i << 1 | 1, mid + 1, r, u, v));
}

main () {
    cin.tie(0)->sync_with_stdio(0);
    if(fopen("task.inp", "r")) {
        freopen("task.inp", "r", stdin);
        freopen("wa.out", "w", stdout);
    }
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    for(int i = n; i >= 1; i--) {
        while (!st.empty() && a[i] > a[st.top()]) {
            opt[i].push_back(st.top());
            st.pop();
        }
        if(!st.empty()) opt[i].push_back(st.top());
        st.push(i);
    }
    cin >> nq;
    for(int i = 1; i <= nq; i++) {
        int l, r; cin >> l >> r;
        q.push_back({i, {l, r}});
    }
    sort(q.begin(), q.end(), [] (pair<int, ii> x, pair<int, ii> y) {
        return x.se.fi > y.se.fi;
    });
    int it = n;
    for(int j = 0; j < nq; j++) {
        int i = q[j].fi, l = q[j].se.fi, r = q[j].se.se;
        while (it >= l) {
            for(int b : opt[it]) upd(1, 1, n, 2 * b - it, n, a[it] + a[b]);
            it--;
        }
        ans[i] = get(1, 1, n, l, r);
    }
    for(int i = 1; i <= nq; i++) cout << ans[i] << "\n";
}

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

jumps.cpp: In function 'void build(int, int, int)':
jumps.cpp:18:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |     int mid = l + r >> 1;
      |               ~~^~~
jumps.cpp: In function 'void down(int)':
jumps.cpp:25:15: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   25 |     if(!down[i]) return ;
      |               ^
jumps.cpp: In function 'void upd(int, int, int, int, int, int)':
jumps.cpp:44:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     int mid = l + r >> 1;
      |               ~~^~~
jumps.cpp: In function 'int get(int, int, int, int, int)':
jumps.cpp:54:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     int mid = l + r >> 1;
      |               ~~^~~
jumps.cpp: At global scope:
jumps.cpp:58:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   58 | main () {
      | ^~~~
jumps.cpp: In function 'int main()':
jumps.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen("wa.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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