Submission #859322

#	Time	Username	Problem	Language	Result	Execution time	Memory
859322		nnhzzz	Triple Jump (JOI19_jumps)	C++14	27 / 100	83 ms	48904 KiB

jumps

#include<bits/stdc++.h>

using namespace std;

#define task "test"
#define REP(i,a,b) for(int i = (a); i<=(b); ++i)
#define REPD(i,a,b) for(int i = (a); i>=(b); --i)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define BIT(x,i) ((x>>i)&1LL)
#define MASK(i) (1LL<<i)
#define fi first
#define se second
#define vi vector<int>
#define pii pair<int,int>
//-----------------------------------------------------------------------//
const int oo = 1e9,LOG = 19,MAXN = MASK(19),N = 1e2+3;
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
//-----------------------------------------------------------------------//
template<typename T> bool mini(T &a, T b){if(a>b){a=b;return true;} return false;}
template<typename T> bool maxi(T &a, T b){if(a<b){a=b;return true;} return false;}

int a[MAXN],lazy[MAXN<<2],res[MAXN];
vector<pii> query[MAXN],adj[MAXN];
int n,q;

struct Node{
    int a,b,v;
    Node(){a = b = v = 0;}
    Node(int a, int b, int v):a(a),b(b),v(v){}
    friend Node operator + (const Node &l, const Node &r){
        return Node(max(l.a,r.a),max(l.b,r.b),max({l.v,r.v,l.a+r.b}));
    }
}seg[MAXN<<1];

void update(int x, int v){
    x |= MAXN;
    maxi(seg[x].a,v);
    seg[x].v = seg[x].a+seg[x].b;
    while(x >>= 1) seg[x] = seg[x<<1]+seg[x<<1|1];
}

int get(int l, int r){
    Node cl,cr; l |= MAXN; r |= MAXN;
    while(l<=r){
        if(l&1) cl = cl+seg[l++];
        if(!r&1) cr = seg[r--]+cr;
        l >>= 1; r >>= 1;
    }
    return (cl+cr).v;
}

void sub4(){
    REP(i,0,MAXN-1) seg[i|MAXN].b = seg[i|MAXN].v = a[i];
    REPD(i,MAXN-1,0) seg[i] = seg[i<<1]+seg[i<<1|1];
    REP(i,1,q){
        int l,r; cin >> l >> r;
        query[l].emplace_back(r,i);
    }
    stack<int> st;
    REP(i,1,n){
        while(SZ(st)!=0){
            int j = st.top();
            adj[j].emplace_back(i,a[i]+a[j]);
            if(a[i]<=a[j]) break;
            st.pop();
        }
        st.push(i);
    }
    REPD(i,n,1){
        for(auto &it:adj[i]){
            int id = it.fi,val = it.se;
            if(id*2-i>n) continue;
            update(id*2-i,val);
        }
        for(auto &it:query[i]){
            int j = it.fi,id = it.se;
            res[id] = get(i,j);
        }
    }
    REP(i,1,q) cout << res[i] << "\n";
}

void solve(){
    cin >> n;
    REP(i,1,n){
        cin >> a[i];
    }
    cin >> q;
    sub4(); return;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    solve();
    return 0;
}

Compilation message (stderr)

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

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