Submission #202859

#	Time	Username	Problem	Language	Result	Execution time	Memory
202859		Mercenary	Triple Jump (JOI19_jumps)	C++14	46 / 100	1591 ms	91512 KiB

jumps

#include<bits/stdc++.h>
#define taskname "A"
#define pb push_back
#define mp make_pair

using namespace std;
const int maxn = 5e5 + 6;
typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
struct node{
    ll lz , s , res;
}s[maxn * 4];
int n , a[maxn];
void push(int x , bool key){
    s[x].res = max(s[x].res,s[x].s+s[x].lz);
    if(key){
        s[x * 2].lz=  max(s[x * 2].lz , s[x].lz);
        s[x * 2 + 1].lz=  max(s[x * 2 +1 ].lz , s[x].lz);
    }
}
void build(int x , int l , int r){
    s[x].lz = -2e9;
    if(l == r){
        s[x].s = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(x*2,l,mid);build(x*2+1,mid+1,r);
    s[x].s = max(s[x*2].s,s[x*2+1].s);
}
void update(int x , int l , int r , int L , int R , ll val){
    push(x,l!=r);
    if(L > r || l > R)return;
    if(L <= l && r <= R){
        s[x].lz = max(s[x].lz,val);
        push(x,l!=r);
        return;
    }
    int mid = l + r >> 1;
    update(x*2,l,mid,L,R,val);
    update(x*2+1,mid+1,r,L,R,val);
    s[x].res = max(s[x*2].res,s[x*2+1].res);
}
ll query(int x , int l , int r , int L , int R){
    push(x,l!=r);
    if(L > r || l > R)return 0;
    if(L <= l && r <= R)return s[x].res;
    int mid = l + r >> 1;
    return max(query(x*2,l,mid,L,R),query(x*2+1,mid+1,r,L,R));
}
int q;
ll ans[maxn];
vector<ii> Q[maxn];
vector<int> U[maxn];

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    if(fopen(taskname".INP","r")){
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)cin >> a[i];
    build(1,1,n);
    vector<int> s;
    for(int i = 1 ; i <= n ; ++i){
        while(s.size() && a[s.back()] <= a[i]){
            U[s.back()].pb(i);s.pop_back();
        }
        if(s.size())U[s.back()].pb(i);
        s.pb(i);
    }
    cin >> q;
    for(int i = 1 ; i <= q ; ++i){
        int u , v;cin >> u >> v;Q[u].pb(mp(v,i));
    }
    for(int i = n ; i >= 1 ; --i){
        for(auto & b : U[i]){
            if(b * 2 - i <= n){
                update(1,1,n,b*2-i,n,a[b]+a[i]);
//                cout << i << " " << b << " " << b * 2 - i << endl;
            }
        }
        for(auto & c : Q[i]){
            ans[c.second] = query(1,1,n,i,c.first);
        }
    }
    for(int i = 1 ; i <= q ; ++i)cout << ans[i] <<  '\n';
}

Compilation message (stderr)

jumps.cpp: In function 'void build(int, int, int)':
jumps.cpp:28:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
jumps.cpp: In function 'void update(int, int, int, int, int, ll)':
jumps.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
jumps.cpp: In function 'll query(int, int, int, int, int)':
jumps.cpp:49:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
jumps.cpp: In function 'int main()':
jumps.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".INP","r",stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".OUT","w",stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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