oj.uz

Submission #585775

# Submission time Handle Problem Language Result Execution time Memory
585775 2022-06-29T10:29:58 Z zaneyu Triple Jump (JOI19_jumps) C++14
100 / 100
 1421 ms 113664 KB 
/*input
5
5 2 1 5 3
3
1 4
2 5
1 5
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#define ld long double
#define pii pair<ll,int>
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
const ll maxn=5e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?" ":"");
    return out;
}
int arr[maxn];
vector<pii> up[maxn],qq[maxn];
struct node{
    int ma=0,mb=0,ans=0;
}seg[4*maxn];
node merge(node a,node b){
    node c;
    c.ans=max({a.ans,b.ans,a.ma+b.mb});
    c.ma=max(a.ma,b.ma);
    c.mb=max(a.mb,b.mb);
    return c;
}
void build(int idx,int l,int r){
    int mid=(l+r)/2;
    seg[idx].mb=arr[l];
    if(l==r) return;
    build(idx*2,l,mid),build(idx*2+1,mid+1,r);
    seg[idx]=merge(seg[idx*2],seg[idx*2+1]);
    //cout<<l<<' '<<r<<' '<<seg[idx].mb<<'\n';
}
void upd(int idx,int l,int r,int p,int x){
    if(r<p or l>p) return;
    if(l==r){
        MXTO(seg[idx].ma,x);
        MXTO(seg[idx].ans,x+seg[idx].mb);
        return;
    }
    int mid=(l+r)/2;
    upd(idx*2,l,mid,p,x),upd(idx*2+1,mid+1,r,p,x);
    seg[idx]=merge(seg[idx*2],seg[idx*2+1]);
}
node query(int idx,int l,int r,int ql,int qr){
    if(ql<=l and r<=qr) return seg[idx];
    int mid=(l+r)/2;
    if(qr<=mid) return query(idx*2,l,mid,ql,qr);
    if(ql>mid) return query(idx*2+1,mid+1,r,ql,qr);
    return merge(query(idx*2,l,mid,ql,qr),query(idx*2+1,mid+1,r,ql,qr));
}
int ans[maxn];
int32_t main(){
    int n;
    cin>>n;
    REP(i,n) cin>>arr[i];
    vector<int> v;
    vector<pii> cand;
    REP(i,n){
        while(sz(v) and arr[v.back()]<=arr[i]) cand.pb({v.back(),i}),v.pop_back();
        if(sz(v)) cand.pb({v.back(),i});
        v.pb(i);
    }
    for(auto x:cand) if(2*x.s-x.f<n) up[x.f].pb({2*x.s-x.f,arr[x.f]+arr[x.s]});
    int q;
    cin>>q;
    REP(i,q){
        int l,r;
        cin>>l>>r;
        --l,--r;
        qq[l].pb({r,i});
    }
    build(1,0,n-1);
    for(int i=n-1;i>=0;i--){
        for(auto x:up[i]) upd(1,0,n-1,x.f,x.s);
        for(auto x:qq[i]){
            ans[x.s]=query(1,0,n-1,i,x.f).ans;
        }
    }
    REP(i,q) cout<<ans[i]<<'\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 12 ms 23792 KB Output is correct
3 Correct 13 ms 23808 KB Output is correct
4 Correct 13 ms 23816 KB Output is correct
5 Correct 12 ms 23788 KB Output is correct
6 Correct 12 ms 23796 KB Output is correct
7 Correct 16 ms 23744 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 13 ms 23796 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 12 ms 23792 KB Output is correct
3 Correct 13 ms 23808 KB Output is correct
4 Correct 13 ms 23816 KB Output is correct
5 Correct 12 ms 23788 KB Output is correct
6 Correct 12 ms 23796 KB Output is correct
7 Correct 16 ms 23744 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 13 ms 23796 KB Output is correct
11 Correct 383 ms 49444 KB Output is correct
12 Correct 406 ms 49196 KB Output is correct
13 Correct 400 ms 49432 KB Output is correct
14 Correct 397 ms 49456 KB Output is correct
15 Correct 392 ms 49524 KB Output is correct
16 Correct 410 ms 48796 KB Output is correct
17 Correct 419 ms 48824 KB Output is correct
18 Correct 379 ms 48680 KB Output is correct
19 Correct 404 ms 49284 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 49004 KB Output is correct
2 Correct 171 ms 41812 KB Output is correct
3 Correct 198 ms 42656 KB Output is correct
4 Correct 240 ms 49028 KB Output is correct
5 Correct 231 ms 49008 KB Output is correct
6 Correct 225 ms 48288 KB Output is correct
7 Correct 244 ms 48164 KB Output is correct
8 Correct 208 ms 48248 KB Output is correct
9 Correct 233 ms 48560 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Correct 12 ms 23792 KB Output is correct
3 Correct 13 ms 23808 KB Output is correct
4 Correct 13 ms 23816 KB Output is correct
5 Correct 12 ms 23788 KB Output is correct
6 Correct 12 ms 23796 KB Output is correct
7 Correct 16 ms 23744 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 13 ms 23796 KB Output is correct
11 Correct 383 ms 49444 KB Output is correct
12 Correct 406 ms 49196 KB Output is correct
13 Correct 400 ms 49432 KB Output is correct
14 Correct 397 ms 49456 KB Output is correct
15 Correct 392 ms 49524 KB Output is correct
16 Correct 410 ms 48796 KB Output is correct
17 Correct 419 ms 48824 KB Output is correct
18 Correct 379 ms 48680 KB Output is correct
19 Correct 404 ms 49284 KB Output is correct
20 Correct 245 ms 49004 KB Output is correct
21 Correct 171 ms 41812 KB Output is correct
22 Correct 198 ms 42656 KB Output is correct
23 Correct 240 ms 49028 KB Output is correct
24 Correct 231 ms 49008 KB Output is correct
25 Correct 225 ms 48288 KB Output is correct
26 Correct 244 ms 48164 KB Output is correct
27 Correct 208 ms 48248 KB Output is correct
28 Correct 233 ms 48560 KB Output is correct
29 Correct 1421 ms 110404 KB Output is correct
30 Correct 1097 ms 92588 KB Output is correct
31 Correct 1116 ms 94508 KB Output is correct
32 Correct 1305 ms 110324 KB Output is correct
33 Correct 1307 ms 110416 KB Output is correct
34 Correct 1244 ms 108116 KB Output is correct
35 Correct 1213 ms 107808 KB Output is correct
36 Correct 1302 ms 107792 KB Output is correct
37 Correct 1334 ms 109252 KB Output is correct
38 Correct 1097 ms 112996 KB Output is correct
39 Correct 1139 ms 113060 KB Output is correct
40 Correct 1082 ms 109648 KB Output is correct
41 Correct 1120 ms 109172 KB Output is correct
42 Correct 1126 ms 109156 KB Output is correct
43 Correct 1141 ms 110876 KB Output is correct
44 Correct 1148 ms 113232 KB Output is correct
45 Correct 1113 ms 113336 KB Output is correct
46 Correct 1056 ms 110120 KB Output is correct
47 Correct 1020 ms 109752 KB Output is correct
48 Correct 1045 ms 109800 KB Output is correct
49 Correct 1048 ms 111780 KB Output is correct
50 Correct 1226 ms 113476 KB Output is correct
51 Correct 1158 ms 113664 KB Output is correct
52 Correct 1104 ms 111076 KB Output is correct
53 Correct 1113 ms 110740 KB Output is correct
54 Correct 1101 ms 110668 KB Output is correct
55 Correct 1122 ms 112336 KB Output is correct