제출 #1157674

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

jumps

#include<bits/stdc++.h>

#define MASK(i) (1 << (i))
#define pub push_back
#define all(v) v.begin(), v.end()
#define compact(v) v.erase(unique(all(v)), end(v))
#define pii pair<int,int>
#define fi first
#define se second
#define endl "\n"
#define sz(v) (int)(v).size()
#define dbg(x) "[" #x " = " << (x) << "]"

using namespace std;

template<class T> bool minimize(T& a, T b){if(a > b) return a = b, true;return false;}
template<class T> bool maximize(T& a, T b){if(a < b) return a = b, true;return false;}

typedef long long ll;
typedef long double ld;

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){return uniform_int_distribution<ll>(l, r)(rng);}

const int N = 1e6 + 15;

int n, q;
int a[N];
vector<int> candidates[N];
vector<pair<int,int>> query[N];
int ans[N];

struct SegmentTree{
    struct node{
        //i < j < k
        //Two = max(a[i] + a[j)
        //One = max(a[k])
        int One, Two, Three;
        node() : One(0), Two(0), Three(0) {}
        node(int One, int Two, int Three) : One(One), Two(Two), Three(Three) {}
    };

    int n;
    vector<node> st;

    SegmentTree(int n) : n(n), st(n << 2) {}

    node merge(node a, node b){
        node c;
        c.Three = max({a.Three, b.Three, a.Two + b.One});
        c.One = max(a.One, b.One);
        c.Two = max(a.Two, b.Two);
        return c;
    }

    void update_one(int l, int r, int id, int pos, int v){
        if(r < pos || l > pos) return;
        if(l == r){
            maximize(st[id].One, v);
            maximize(st[id].Three, st[id].One + st[id].Two);
            return;
        }
        int mid = (l+r) >> 1;
        update_one(l,mid,id<<1,pos,v);
        update_one(mid+1,r,id<<1|1,pos,v);
        st[id] = merge(st[id<<1], st[id<<1|1]);
    }

    void update_two(int l, int r, int id, int pos, int v){
        if(r < pos || l > pos) return;
        if(l == r){
            maximize(st[id].Two, v);
            maximize(st[id].Three, st[id].One + st[id].Two);
            return;
        }
        int mid = (l+r) >> 1;
        update_two(l,mid,id<<1,pos,v);
        update_two(mid+1,r,id<<1|1,pos,v);
        st[id] = merge(st[id<<1], st[id<<1|1]);
    }

    node get(int l, int r, int id, int u, int v){
        if(r < u || l > v) return node();
        if(u <= l && r <= v) return st[id];
        int mid = (l+r) >> 1;
        return merge(get(l,mid,id<<1,u,v), get(mid+1,r,id<<1|1,u,v));
    }
};

void solve(){
    cin >> n;

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

    stack<int> ST;

    auto add_candidates = [&](int i, int j) -> void{
        if(2*j - i <= n) candidates[i].push_back(j);// cout << i << " " << j << endl;
    };

    for(int i = 1; i <= n; i++){
        //cout << dbg(i) << endl;
        while(!ST.empty() && a[ST.top()] <= a[i]){
            //cout << "of 1: \n";
            add_candidates(ST.top(), i);
            ST.pop();
        }
        //cout << "of 2: \n";
        if(!ST.empty()) add_candidates(ST.top(), i);
        ST.push(i);
    }

    cin >> q;

    for(int i = 1; i <= q; i++){
        int l, r; cin >> l >> r;
        query[l].push_back(pii(r,i));
    }

    SegmentTree st(n);

    for(int i = n; i >= 1; i--){
        st.update_one(1,n,1,i,a[i]);
        for(int j : candidates[i]){
            int k = 2*j - i;
            st.update_two(1,n,1,k,a[i] + a[j]);
            //cout << k << " " << a[i] + a[j] << endl;
            //cout << "---" << endl;
        }
        for(auto [j, id] : query[i]){
            ans[id] = st.get(1,n,1,i,j).Three;
        }
    }

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

signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(0); cout.tie(0);

    #define task "task"

    if(fopen(task".INP", "r")){
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    int t; t = 1; //cin >> t;
    while(t--) solve();
}

/*
    i < j < k
    +) j - i <= k - j
    <=> 2*j - i <= k
    <=> 2*j/i <= k

    --> (i) is inversly proportional to (k)

    for each i, find some important point j, update for range[k;n]

    larger the i, larger range [k;n]

    +) offline:

    for(i : n -> 1) answer query with lb is (i)

    +) consider query [L;R] with:

    L <= x < y < z <= R
    a[x] > a[y] > a[z]

    z is not important to x:
        a[x] + a[y] > a[x] + a[z] --> (x,y) is more valuable
        y - x <= z - x             --> (x,y) gives a better range of [k; r]

    --> only pick (x,y) or (y,z)

    --> use stack max from 1 -> n: match (i) with the back of the stack
        *) 2*i - st.back() <= n --> (i) is important to st.back()
    +) [L;mid]  : max(a[i] + a[j])
       [mid+1;R]: max(a[k])
       --> segment tree merge nodes
*/

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

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

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