oj.uz

Submission #742316

# Submission time Handle Problem Language Result Execution time Memory
742316 2023-05-16T05:53:40 Z bgnbvnbv Triple Jump (JOI19_jumps) C++14
100 / 100
 1052 ms 106388 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=5e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
struct node
{
    ll f,s,val;
    node()
    {
        f=-inf;
        s=-inf;
        val=-inf;
    }
    node operator+(const node&o)
    {
        node ans;
        ans.f=max(f,o.f);
        ans.s=max(s,o.s);
        ans.val=max({-inf,val,o.val,f+o.s});
        return ans;
    }
}st[4*maxN];
ll n;
//ll st[4*maxN];
void update(ll t,ll pos,ll val,ll id=1,ll l=1,ll r=n)
{
    if(pos>r||pos<l) return ;
    if(l==r)
    {
        if(t==1) st[id].f=max(st[id].f,val);
        else st[id].s=max(st[id].s,val);
        st[id].val=max(-inf,st[id].f+st[id].s);
        return;
    }
    ll mid=l+r>>1;
    if(pos<=mid) update(t,pos,val,id*2,l,mid);
    else update(t,pos,val,id*2+1,mid+1,r);
    st[id]=st[id*2]+st[id*2+1];
}
node get(ll i,ll j,ll id=1,ll l=1,ll r=n)
{
    if(j<l||r<i) return node();
    if(i<=l&&r<=j) return st[id];
    ll mid=l+r>>1;
    return get(i,j,id*2,l,mid)+get(i,j,id*2+1,mid+1,r);
}
ll q;
ll a[maxN];
vector<pli>adu[maxN];
ll ans[maxN];
void solve()
{
    cin >> n;
    deque<int>dq;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        update(0,i,a[i]);
    }
    cin >> q;
    for(int i=1;i<=q;i++)
    {
        ll l,r;
        cin >> l >> r;
        adu[l].pb({r,i});
    }
    vector<pli>vd;
    for(int i=1;i<=n;i++)
    {
        while(dq.size()>0&&a[i]>=a[dq.back()])
        {
            vd.pb({dq.back(),i});
            dq.pop_back();
        }
        if(dq.size()>0)
        {
            vd.pb({dq.back(),i});
        }
        dq.pb(i);
    }
    sort(vd.begin(),vd.end());
    ll j=(int)vd.size()-1;
    for(int i=n;i>=1;i--)
    {
        while(j>=0&&vd[j].fi>=i)
        {
            update(1,vd[j].se*2-vd[j].fi,a[vd[j].fi]+a[vd[j].se]);
            j--;
        }
        for(auto zz:adu[i])
        {
            ans[zz.se]=get(i,zz.fi).val;
        }
    }
    for(int i=1;i<=q;i++) cout << ans[i]<<'\n';
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

jumps.cpp: In function 'void update(ll, ll, ll, ll, ll, ll)':
jumps.cpp:43:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     ll mid=l+r>>1;
      |            ~^~
jumps.cpp: In function 'node get(ll, ll, ll, ll, ll)':
jumps.cpp:52:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     ll mid=l+r>>1;
      |            ~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 58904 KB Output is correct
2 Correct 26 ms 58964 KB Output is correct
3 Correct 31 ms 58924 KB Output is correct
4 Correct 26 ms 58956 KB Output is correct
5 Correct 27 ms 59024 KB Output is correct
6 Correct 26 ms 58944 KB Output is correct
7 Correct 29 ms 59024 KB Output is correct
8 Correct 29 ms 59032 KB Output is correct
9 Correct 26 ms 58964 KB Output is correct
10 Correct 26 ms 58956 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 58904 KB Output is correct
2 Correct 26 ms 58964 KB Output is correct
3 Correct 31 ms 58924 KB Output is correct
4 Correct 26 ms 58956 KB Output is correct
5 Correct 27 ms 59024 KB Output is correct
6 Correct 26 ms 58944 KB Output is correct
7 Correct 29 ms 59024 KB Output is correct
8 Correct 29 ms 59032 KB Output is correct
9 Correct 26 ms 58964 KB Output is correct
10 Correct 26 ms 58956 KB Output is correct
11 Correct 307 ms 79820 KB Output is correct
12 Correct 318 ms 79748 KB Output is correct
13 Correct 295 ms 79836 KB Output is correct
14 Correct 291 ms 79872 KB Output is correct
15 Correct 283 ms 79848 KB Output is correct
16 Correct 285 ms 79148 KB Output is correct
17 Correct 322 ms 79080 KB Output is correct
18 Correct 323 ms 79016 KB Output is correct
19 Correct 299 ms 79628 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 64836 KB Output is correct
2 Correct 119 ms 62756 KB Output is correct
3 Correct 118 ms 63148 KB Output is correct
4 Correct 184 ms 64768 KB Output is correct
5 Correct 191 ms 64764 KB Output is correct
6 Correct 185 ms 64784 KB Output is correct
7 Correct 185 ms 64836 KB Output is correct
8 Correct 205 ms 64756 KB Output is correct
9 Correct 181 ms 64808 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 58904 KB Output is correct
2 Correct 26 ms 58964 KB Output is correct
3 Correct 31 ms 58924 KB Output is correct
4 Correct 26 ms 58956 KB Output is correct
5 Correct 27 ms 59024 KB Output is correct
6 Correct 26 ms 58944 KB Output is correct
7 Correct 29 ms 59024 KB Output is correct
8 Correct 29 ms 59032 KB Output is correct
9 Correct 26 ms 58964 KB Output is correct
10 Correct 26 ms 58956 KB Output is correct
11 Correct 307 ms 79820 KB Output is correct
12 Correct 318 ms 79748 KB Output is correct
13 Correct 295 ms 79836 KB Output is correct
14 Correct 291 ms 79872 KB Output is correct
15 Correct 283 ms 79848 KB Output is correct
16 Correct 285 ms 79148 KB Output is correct
17 Correct 322 ms 79080 KB Output is correct
18 Correct 323 ms 79016 KB Output is correct
19 Correct 299 ms 79628 KB Output is correct
20 Correct 179 ms 64836 KB Output is correct
21 Correct 119 ms 62756 KB Output is correct
22 Correct 118 ms 63148 KB Output is correct
23 Correct 184 ms 64768 KB Output is correct
24 Correct 191 ms 64764 KB Output is correct
25 Correct 185 ms 64784 KB Output is correct
26 Correct 185 ms 64836 KB Output is correct
27 Correct 205 ms 64756 KB Output is correct
28 Correct 181 ms 64808 KB Output is correct
29 Correct 985 ms 100748 KB Output is correct
30 Correct 841 ms 96776 KB Output is correct
31 Correct 836 ms 98784 KB Output is correct
32 Correct 988 ms 100780 KB Output is correct
33 Correct 999 ms 100692 KB Output is correct
34 Correct 1052 ms 98424 KB Output is correct
35 Correct 991 ms 98132 KB Output is correct
36 Correct 968 ms 98156 KB Output is correct
37 Correct 1018 ms 99560 KB Output is correct
38 Correct 775 ms 106388 KB Output is correct
39 Correct 719 ms 106356 KB Output is correct
40 Correct 727 ms 103040 KB Output is correct
41 Correct 712 ms 102504 KB Output is correct
42 Correct 728 ms 102576 KB Output is correct
43 Correct 733 ms 104232 KB Output is correct
44 Correct 889 ms 105756 KB Output is correct
45 Correct 865 ms 105740 KB Output is correct
46 Correct 763 ms 102756 KB Output is correct
47 Correct 784 ms 102268 KB Output is correct
48 Correct 804 ms 102136 KB Output is correct
49 Correct 758 ms 104244 KB Output is correct
50 Correct 819 ms 104000 KB Output is correct
51 Correct 883 ms 103888 KB Output is correct
52 Correct 820 ms 101448 KB Output is correct
53 Correct 831 ms 101156 KB Output is correct
54 Correct 832 ms 101040 KB Output is correct
55 Correct 795 ms 102728 KB Output is correct