oj.uz

Submission #944158

# Submission time Handle Problem Language Result Execution time Memory
944158 2024-03-12T09:13:55 Z beepbeepsheep Triple Jump (JOI19_jumps) C++17
19 / 100
 1803 ms 199828 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll int
#define ii pair<ll,ll>
#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif

const ll maxn=5005;
const ll inf=1e15;
ll arr[maxn];
struct node{
    ll s,e,m,val;
    node *l,*r;
    node (ll _s, ll _e){
        s=_s,e=_e,m=(s+e)>>1,val=0;
        if (s!=e) l=new node(s,m),r=new node(m+1,e);
    }
    void upd(ll x, ll v){
        if (s==e){
            val=max(v,val);
            return;
        }
        if (x>m) r->upd(x,v);
        else l->upd(x,v);
        val=max(l->val,r->val);
    }
    ll query(ll x, ll y){
        if (x<=s && e<=y) return val;
        if (x>m) return r->query(x,y);
        if (y<=m) return l->query(x,y);
        return max(l->query(x,y),r->query(x,y));
    }
}*root,*rmq;
ll n;
vector<tuple<ll,ll,ll>> v,q;
ll ans[500005];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    root=new node(1,n);
    for (int i=1;i<=n;i++) cin>>arr[i],root->upd(i,arr[i]);
    for (int i=1;i<=n;i++){
        for (int j=i+2;j<=n;j++){
            v.emplace_back(i,j,arr[i]+arr[j]+
                           root->query(i+1,(i+j)>>1));
            //cerr<<i<<' '<<j<<' '<<arr[i]+arr[j]+root->query(i+1,(i+j)>>1)<<endl;
        }
    }
    sort(v.rbegin(),v.rend());
    rmq=new node(1,n);
    ll qu,l,r;
    cin>>qu;
    for (int i=1;i<=qu;i++){
        cin>>l>>r;
        q.emplace_back(l,r,i);
    }
    sort(q.rbegin(),q.rend());
    ll ptr=0;
    for (auto [l,r,i]:q){
        while (ptr!=v.size() && l<=get<0>(v[ptr])){
            rmq->upd(get<1>(v[ptr]),get<2>(v[ptr]));
            ptr++;
        }
        ans[i]=rmq->query(l,r);
    }
    for (int i=1;i<=qu;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}

Compilation message

jumps.cpp:12:14: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+15' to '2147483647' [-Woverflow]
   12 | const ll inf=1e15;
      |              ^~~~
jumps.cpp: In function 'int main()':
jumps.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         while (ptr!=v.size() && l<=get<0>(v[ptr])){
      |                ~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1749 ms 199004 KB Output is correct
12 Correct 1769 ms 198032 KB Output is correct
13 Correct 1759 ms 198156 KB Output is correct
14 Correct 1783 ms 198552 KB Output is correct
15 Correct 1784 ms 198040 KB Output is correct
16 Correct 1752 ms 198040 KB Output is correct
17 Correct 1803 ms 198044 KB Output is correct
18 Correct 1774 ms 199828 KB Output is correct
19 Correct 1753 ms 198304 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 38564 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 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1749 ms 199004 KB Output is correct
12 Correct 1769 ms 198032 KB Output is correct
13 Correct 1759 ms 198156 KB Output is correct
14 Correct 1783 ms 198552 KB Output is correct
15 Correct 1784 ms 198040 KB Output is correct
16 Correct 1752 ms 198040 KB Output is correct
17 Correct 1803 ms 198044 KB Output is correct
18 Correct 1774 ms 199828 KB Output is correct
19 Correct 1753 ms 198304 KB Output is correct
20 Runtime error 29 ms 38564 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -