oj.uz

Submission #1013605

# Submission time Handle Problem Language Result Execution time Memory
1013605 2024-07-03T17:20:23 Z ReLice Triple Jump (JOI19_jumps) C++17
19 / 100
 285 ms 42836 KB 
#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>*/
template<class S,class T>
bool chmin(S &a,const T &b) {
	return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
	return a<b?(a=b)==b:false;
}
//void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=1e18;
const ll mod=998244353;
const ll N=1.2e5+7;
const ld eps=1e-9;
struct node{
    ll ans,ab,c;
    node operator + (node b){
        node x;
        x.ans=max(ans,b.ans);
        x.ab=max(ab,b.ab);
        x.c=max(c,b.c);
        return x;
    }
};
vector<node> t(N*4);
vll add(N*4);
ll a[N];
void build(ll v,ll tl,ll tr){
    if(tl==tr){
        t[v]={a[tl],0ll,a[tl]};
        return;
    }
    ll tm=(tl+tr)/2;
    build(v*2,tl,tm);
    build(v*2+1,tm+1,tr);
    t[v]=t[v*2]+t[v*2+1];
}
void push(ll v,ll tl,ll tr){
    if(tl!=tr){
        chmax(add[v*2],add[v]);
        chmax(add[v*2+1],add[v]);
    }
    chmax(t[v].ab,add[v]);
    chmax(t[v].ans,t[v].c+add[v]);
    add[v]=0;
}
void upd(ll l,ll r,ll val,ll v,ll tl,ll tr){
    push(v,tl,tr);
    if(tl>r || tr<l)return ;
    if(l<=tl && tr<=r){
        add[v]=val;
        push(v,tl,tr);
        return;
    }
    ll tm=(tl+tr)/2;
    upd(l,r,val,v*2,tl,tm);
    upd(l,r,val,v*2+1,tm+1,tr);
    t[v]=t[v]+t[v*2];
    t[v]=t[v]+t[v*2+1];
}
ll get(ll l,ll r,ll v,ll tl,ll tr){
    push(v,tl,tr);
    if(tl>r || tr<l)return 0ll;
    if(l<=tl && tr<=r){
        //cout<<tl<<' '<<tr<<endl;
        //cout<<t[v].ans<<' '<<t[v].ab<<' '<<t[v].c<<endl;
        return t[v].ans;
    }
    ll tm=(tl+tr)/2;
    return max(get(l,r,v*2,tl,tm),get(l,r,v*2+1,tm+1,tr));
}
void solve(){
    ll i,j;
    ll n,q;
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    cin>>q;
    vector<pll> qq(n+5);
    for(i=0;i<q;i++){
        ll l,r;
        cin>>l>>r;
        qq[l].pb({r,i});
    }
    ll ans[q];
    pll cur;
    for(i=n;i>0;i--){
        while(cur.sz && cur.bc.fr<a[i]){
            ll A=i,B=cur.bc.sc;
            //cout<<a[A]<<' '<<a[B]<<endl;
            if(2*B-A<=n)upd(2*B-A,n,a[i]+a[B],1,1,n);
            cur.pob;
        }
        if(cur.sz){
            ll A=i,B=cur.bc.sc;
            //cout<<a[A]<<' '<<a[B]<<endl;
            if(2*B-A<=n)upd(2*B-A,n,a[i]+a[B],1,1,n);
        }
        cur.pb({a[i],i});
        for(auto j : qq[i]){
            ans[j.sc]=get(i,j.fr,1,1,n);
        }
    }
    for(i=0;i<q;i++) cout<<ans[i]<<endl;
}
signed main(){
    start();
    ll t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}
/*



*/

Compilation message

jumps.cpp: In function 'void solve()':
jumps.cpp:103:10: warning: unused variable 'j' [-Wunused-variable]
  103 |     ll i,j;
      |          ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15452 KB Output is correct
2 Correct 6 ms 15452 KB Output is correct
3 Correct 7 ms 15452 KB Output is correct
4 Correct 6 ms 15508 KB Output is correct
5 Correct 6 ms 15264 KB Output is correct
6 Correct 6 ms 15452 KB Output is correct
7 Correct 6 ms 15452 KB Output is correct
8 Correct 6 ms 15328 KB Output is correct
9 Correct 6 ms 15452 KB Output is correct
10 Correct 6 ms 15452 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15452 KB Output is correct
2 Correct 6 ms 15452 KB Output is correct
3 Correct 7 ms 15452 KB Output is correct
4 Correct 6 ms 15508 KB Output is correct
5 Correct 6 ms 15264 KB Output is correct
6 Correct 6 ms 15452 KB Output is correct
7 Correct 6 ms 15452 KB Output is correct
8 Correct 6 ms 15328 KB Output is correct
9 Correct 6 ms 15452 KB Output is correct
10 Correct 6 ms 15452 KB Output is correct
11 Correct 271 ms 42692 KB Output is correct
12 Correct 250 ms 42836 KB Output is correct
13 Correct 269 ms 42636 KB Output is correct
14 Correct 243 ms 42500 KB Output is correct
15 Correct 269 ms 42576 KB Output is correct
16 Correct 285 ms 42064 KB Output is correct
17 Correct 256 ms 42052 KB Output is correct
18 Correct 246 ms 41812 KB Output is correct
19 Correct 255 ms 42576 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 34128 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15452 KB Output is correct
2 Correct 6 ms 15452 KB Output is correct
3 Correct 7 ms 15452 KB Output is correct
4 Correct 6 ms 15508 KB Output is correct
5 Correct 6 ms 15264 KB Output is correct
6 Correct 6 ms 15452 KB Output is correct
7 Correct 6 ms 15452 KB Output is correct
8 Correct 6 ms 15328 KB Output is correct
9 Correct 6 ms 15452 KB Output is correct
10 Correct 6 ms 15452 KB Output is correct
11 Correct 271 ms 42692 KB Output is correct
12 Correct 250 ms 42836 KB Output is correct
13 Correct 269 ms 42636 KB Output is correct
14 Correct 243 ms 42500 KB Output is correct
15 Correct 269 ms 42576 KB Output is correct
16 Correct 285 ms 42064 KB Output is correct
17 Correct 256 ms 42052 KB Output is correct
18 Correct 246 ms 41812 KB Output is correct
19 Correct 255 ms 42576 KB Output is correct
20 Runtime error 25 ms 34128 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -