Submission #923086

#	Time	Username	Problem	Language	Result	Execution time	Memory
923086		phoenix0423	Triple Jump (JOI19_jumps)	C++17	100 / 100	943 ms	153828 KiB

jumps

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define FOR(i, n) for(int i = 0; i < n; i++)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#define int long long
const ll INF = 1e18;
const int maxn = 5e5 + 5;
int n;

struct info{
    int l, r, t, id;
    info(){}
    info(int _l, int _r, int _t, int _id) : l(_l), r(_r), t(_t), id(_id){}
    bool operator < (const info& other) const{
        if(l != other.l) return l < other.l;
        return t < other.t;
    }
    bool operator > (const info& other) const{
        if(l != other.l) return l > other.l;
        return t > other.t;
    }
};

struct node{
    int f, mx, ttl, tag;
};
node st[maxn * 4];
void cast(int v, int val){
    st[v].f = max(st[v].f, val);
    st[v].tag = max(st[v].tag, val);
    st[v].ttl = max(st[v].ttl, st[v].f + st[v].mx);
}
void push(int v){
    if(st[v].tag){
        cast(v * 2, st[v].tag);
        cast(v * 2 + 1, st[v].tag);
        st[v].tag = 0;
    }
}
void upd(int l, int r, pll val, int v = 1, int L = 0, int R = n - 1){
    if(l > R || r < L) return;
    if(l <= L && r >= R){
        st[v].f = max(st[v].f, val.f);
        st[v].mx = max(st[v].mx, val.s);
        st[v].tag = max(st[v].tag, val.f);
        st[v].ttl = max(st[v].ttl, st[v].f + st[v].mx);
        return;
    }
    push(v);
    int m = (L + R) / 2;
    upd(l, r, val, v * 2, L, m);
    upd(l, r, val, v * 2 + 1, m + 1, R);
    st[v].ttl = max(st[v * 2].ttl, st[v * 2 + 1].ttl);
    st[v].mx = max(st[v * 2].mx, st[v * 2 + 1].mx);
}

int qry(int l, int r, int v = 1, int L = 0, int R = n - 1){
    if(l > R || r < L) return 0;
    if(l <= L && r >= R) return st[v].ttl;
    push(v);
    int m = (L + R) / 2;
    return max(qry(l, r, v * 2, L, m), qry(l, r, v * 2 + 1, m + 1, R));
}
signed main(void){
    fastio;
    cin>>n;
    for(int i = 0; i < n * 4; i++) st[i].f = st[i].mx = st[i].ttl = -INF;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin>>a[i];
    int q;
    cin>>q;
    vector<pll> rng;
    stack<int> stk;
    stk.push(0);
    for(int i = 1; i < n; i++){
        while(!stk.empty() && a[stk.top()] <= a[i]){
            rng.eb(stk.top(), i);
            stk.pop();
        }
        if(!stk.empty()){
            rng.eb(stk.top(), i);
        }
        stk.push(i);
    }
    vector<info> event;
    for(auto [x, y] : rng){
        // cout<<"ok : "<<x<<" "<<y<<"\n";
        if(2 * y - x < n) event.pb(info(x, 2 * y - x, 1, a[x] + a[y]));
    }
    for(int i = 0; i < q; i++){
        int l, r;
        cin>>l>>r;
        l--, r--;
        event.pb(info(l, r, 0, i));
    }
    sort(event.begin(), event.end(), greater<info>());
    for(int i = 0; i < n; i++) upd(i, i, {-INF, a[i]});
    vector<int> ans(q);
    for(int i = 0; i < event.size(); i++){
        int t = event[i].l;
        while(i < event.size() && event[i].l == t){
            auto [l, r, t, id] = event[i];
            // cout<<"event : "<<l<<" "<<r<<" "<<t<<" "<<id<<"\n";
            i++;
            if(t) upd(r, n - 1, {id, -INF});
            else{
                ans[id] = qry(l, r);
                // cout<<"qry : "<<qry(l, r)<<"\n";
            }
        }
        i--;
    }
    for(auto x : ans) cout<<x<<"\n";
    cout<<"\n";
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:106:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for(int i = 0; i < event.size(); i++){
      |                    ~~^~~~~~~~~~~~~~
jumps.cpp:108:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         while(i < event.size() && event[i].l == t){
      |               ~~^~~~~~~~~~~~~~

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