oj.uz

Submission #993557

# Submission time Handle Problem Language Result Execution time Memory
993557 2024-06-06T04:56:40 Z imarn Triple Jump (JOI19_jumps) C++14
46 / 100
 242 ms 30128 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int mxn=3e5+5;
int a[mxn];
struct node{
    int mx,mxf,mxa;
    node operator+(node b){
        node rs;
        rs.mx=max({mx,b.mx,mxf+b.mxa});
        rs.mxf=max(mxf,b.mxf);
        rs.mxa=max(mxa,b.mxa);
        return rs;
    }
}t[4*mxn];
void build(int i,int l,int r){
    if(l==r)return void(t[i]={0,0,a[l]});
    int m=(l+r)>>1;build(2*i,l,m);build(2*i+1,m+1,r);
    t[i]=t[2*i]+t[2*i+1];
}
void update(int i,int l,int r,int idx,int v){
    if(r<idx||l>idx)return;
    if(l==r){
        t[i].mxf=max(t[i].mxf,v);
        t[i].mx=t[i].mxf+t[i].mxa;
        return;
    }int m=(l+r)>>1;update(2*i,l,m,idx,v);update(2*i+1,m+1,r,idx,v);
    t[i]=t[2*i]+t[2*i+1];
}
node query(int i,int l,int r,int tl,int tr){
    if(r<tl||l>tr)return {0,0,0};
    if(r<=tr&&l>=tl)return t[i];
    int m=(l+r)>>1;
    return query(2*i,l,m,tl,tr)+query(2*i+1,m+1,r,tl,tr);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    stack<int>st;vector<pii>gd;
    for(int i=1;i<=n;i++){
        while(!st.empty()&&a[st.top()]<=a[i])gd.pb({st.top(),i}),st.pop();
        if(!st.empty())gd.pb({st.top(),i});st.push(i);
    }int id=0;build(1,1,n);
    int q;cin>>q;int ans[q+1];
    vector<pii>qr[n+1];
    for(int i=1;i<=q;i++){
        int l,r;cin>>l>>r;
        qr[l].pb({r,i});
    }sort(gd.rbegin(),gd.rend());
    for(int l=n;l>=1;l--){
        while(id<gd.size()&&gd[id].f>=l){id++;
            int idx=gd[id-1].s*2-gd[id-1].f;
            if(idx>n){continue;}
            update(1,1,n,idx,a[gd[id-1].f]+a[gd[id-1].s]);
        }
        for(auto it : qr[l]){
            ans[it.s]=query(1,1,n,l,it.f).mx;
        }
    }for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:48:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   48 |         if(!st.empty())gd.pb({st.top(),i});st.push(i);
      |         ^~
jumps.cpp:48:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   48 |         if(!st.empty())gd.pb({st.top(),i});st.push(i);
      |                                            ^~
jumps.cpp:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         while(id<gd.size()&&gd[id].f>=l){id++;
      |               ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 242 ms 29908 KB Output is correct
12 Correct 228 ms 29780 KB Output is correct
13 Correct 238 ms 30032 KB Output is correct
14 Correct 224 ms 29848 KB Output is correct
15 Correct 221 ms 30128 KB Output is correct
16 Correct 225 ms 29460 KB Output is correct
17 Correct 233 ms 29252 KB Output is correct
18 Correct 228 ms 29144 KB Output is correct
19 Correct 228 ms 29944 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 22216 KB Output is correct
2 Correct 50 ms 18896 KB Output is correct
3 Correct 50 ms 19948 KB Output is correct
4 Correct 103 ms 22476 KB Output is correct
5 Correct 109 ms 23496 KB Output is correct
6 Correct 107 ms 22988 KB Output is correct
7 Correct 108 ms 22720 KB Output is correct
8 Correct 102 ms 22976 KB Output is correct
9 Correct 109 ms 21960 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 242 ms 29908 KB Output is correct
12 Correct 228 ms 29780 KB Output is correct
13 Correct 238 ms 30032 KB Output is correct
14 Correct 224 ms 29848 KB Output is correct
15 Correct 221 ms 30128 KB Output is correct
16 Correct 225 ms 29460 KB Output is correct
17 Correct 233 ms 29252 KB Output is correct
18 Correct 228 ms 29144 KB Output is correct
19 Correct 228 ms 29944 KB Output is correct
20 Correct 111 ms 22216 KB Output is correct
21 Correct 50 ms 18896 KB Output is correct
22 Correct 50 ms 19948 KB Output is correct
23 Correct 103 ms 22476 KB Output is correct
24 Correct 109 ms 23496 KB Output is correct
25 Correct 107 ms 22988 KB Output is correct
26 Correct 108 ms 22720 KB Output is correct
27 Correct 102 ms 22976 KB Output is correct
28 Correct 109 ms 21960 KB Output is correct
29 Runtime error 22 ms 8788 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -