제출 #1275625

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275625		monaxia	3단 점프 (JOI19_jumps)	C++20	32 / 100	113 ms	37096 KiB

jumps

#include <bits/stdc++.h>
#include <ext/random>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define vektor vector

using namespace std;
// using namespace __gnu_pbds; 

using ll = long long;
using ull = unsigned long long;
using ld = long double;

constexpr ull Mod = 1e9 + 7;
constexpr ull Mod2 = 1 + 7 * 17 * (1 << 23);
constexpr ull sqr = 320;
constexpr ld eps = 1e-9;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random(ll l, ll r) {if(l <= r) return uniform_int_distribution <ll> (l, r)(rng); return -1;} 

ll st[800005], lazy[800005], st2[800005];
ll a[800005];

void build(int idx, int l, int r, ll a[]){
    if(l == r){
        st2[idx] = a[l];
        st[idx] = a[l];

        return;
    }

    int mid = (l + r) >> 1;

    build(idx << 1, l, mid, a);
    build(idx << 1 | 1, mid + 1, r, a);

    st2[idx] = max(st2[idx << 1], st2[idx << 1 | 1]);
    st[idx] = st2[idx];

}

void update(int idx, int l, int r, int u, int v, ll val){
    if(v < u) return;
    if(lazy[idx] != 0){
        st[idx] = max(st[idx], st2[idx] + lazy[idx]);

        if(l != r){
            lazy[idx << 1] = max(lazy[idx << 1], lazy[idx]);
            lazy[idx << 1 | 1] = max(lazy[idx << 1 | 1], lazy[idx]);
        }

        lazy[idx] = 0;
    }

    if(v < l || r < u) return;
    if(u <= l && r <= v){
        st[idx] = max(st[idx], val + st2[idx]);

        if(l != r){
            lazy[idx << 1] = max(lazy[idx << 1], val);
            lazy[idx << 1 | 1] = max(lazy[idx << 1 | 1], val);
        }

        return;
    }

    int mid = (l + r) >> 1;

    update(idx << 1, l, mid, u, v, val);
    update(idx << 1 | 1, mid + 1, r, u, v, val);

    st[idx] = max(st[idx << 1], st[idx << 1 | 1]);
}

int query(int idx, int l, int r, int u, int v){
    if(v < u) return 0;
    if(lazy[idx] != 0){
        st[idx] = max(st[idx], st2[idx] + lazy[idx]);
        
        if(l != r){
            lazy[idx << 1] = max(lazy[idx << 1], lazy[idx]);
            lazy[idx << 1 | 1] = max(lazy[idx << 1 | 1], lazy[idx]);
        }

        lazy[idx] = 0;
    }

    if(v < l || r < u) return 0;

    if(u <= l && r <= v) {
        return st[idx];
    }

    int mid = (l + r) >> 1;

    return max(query(idx << 1, l, mid, u, v), query(idx << 1 | 1, mid + 1, r, u, v)); 
}

void solve(){
    memset(st, 0, sizeof(st));
    memset(lazy, 0, sizeof(st));

    int n;
    cin >> n;

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

    vector <ll> rr[n + 1];

    stack <int> stt;
    
    for(int i = 1; i <= n; i ++){
        while(!stt.empty()){
            rr[stt.top()].pb(i);
            if(a[stt.top()] > a[i]) break;
            stt.pop();
        }

        stt.push(i);
    }

    build(1, 1, n, a);

    vector <pair <int, int>> quer[n + 1];
    ll ans[n + 1];

    int Q;
    cin >> Q;

    for(int i = 1; i <= Q; i ++){
        int l, r;
        cin >> l >> r;

        quer[l].pb({r, i});
    }

    for(int i = n; i >= 1; i --){
        for(auto& x : rr[i]) {
            update(1, 1, n, 2 * x - i, n, a[i] + a[x]);
            // cout << i << " " << x << " " << a[i] + a[x] << ": " << 2 * x - i << "->" << n << "\n";
        }

        for(auto& x : quer[i]) ans[x.sc] = query(1, 1, n, i, x.fr);
    }

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

int main(){
    // cout << 1; return 0;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 

    if(fopen("TABLE.inp", "r")){
        freopen("TABLE.inp", "r", stdin);
        freopen("TABLE.out", "w", stdout);
    }

    ll t = 1;

    // for if the problem requires multitest

    // cin >> t;

    while(t --){
        solve();
        cout << "\n";
    }

    cerr << "Code time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}



// Whose eyes are those eyes?

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

jumps.cpp: In function 'int main()':
jumps.cpp:164:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |         freopen("TABLE.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:165:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |         freopen("TABLE.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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