oj.uz

Submission #236832

# Submission time Handle Problem Language Result Execution time Memory
236832 2020-06-03T14:02:46 Z egekabas Triple Jump (JOI19_jumps) C++14
0 / 100
 277 ms 81036 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pii;
typedef pair<ull, ull>    pull;
typedef pair<ld, ld>  pld;
ll sfunc(pii a, pii b){
    return a.ss < b.ss;
}
vector<pii> merge(vector<pii> v1, vector<pii> v2){
    vector<pii> ret;
    ll i = 0, j = 0;
    while(ret.size() < 20 && (i < v1.size() || j < v2.size())){
        if(i == v1.size())
            ret.pb(v2[j++]);
        else if(j == v2.size())
            ret.pb(v1[i++]);
        else if(v1[i].ff > v2[j].ff)
            ret.pb(v1[i++]);
        else    
            ret.pb(v2[j++]);
    }
    return ret;
}
ll a[500009];
vector<pii> seg[2000000];
void build(ll v, ll tl, ll tr){
    if(tl == tr){
        seg[v].pb(mp(a[tl], tl));
        return;
    }
    build(2*v, tl, (tl+tr)/2);
    build(2*v+1, (tl+tr)/2+1, tr);
    seg[v] = merge(seg[2*v], seg[2*v+1]);
}
vector<pii> get(ll v, ll tl, ll tr, ll l, ll r){
    if(tr < l || tl > r)
        return {};
    else if(l <= tl && tr <= r)
        return seg[v];
    else{
        ll tm = (tl+tr)/2;
        return merge(get(2*v, tl, tm, l, r), get(2*v+1, tm+1, tr, l, r));
    }
}
ll n;
ll q;
ll solve(ll l, ll r){
    vector<pii> v = get(1, 0, n-1, l, r);
    ll ans = 0;
    sort(v.begin(), v.end(), sfunc);
    for(ll i1 = 0; i1 < v.size(); ++i1)
        for(ll i2 = i1+1; i2 < v.size(); ++i2)
            for(ll i3 = i2+1; i3 < v.size(); ++i3)
                if(v[i2].ss-v[i1].ss <= v[i3].ss-v[i2].ss)
                    ans = max(ans, v[i1].ff+v[i2].ff+v[i3].ff);
    return ans;
}
int main() {
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n;
    for(ll i = 0; i < n; ++i)
        cin >> a[i];
    build(1, 0, n-1);
    cin >> q;
    while(q--){
        ll l, r;
        cin >> l >> r;
        cout << solve(l-1, r-1) << '\n';
    }
}

Compilation message

jumps.cpp: In function 'std::vector<std::pair<long long int, long long int> > merge(std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >)':
jumps.cpp:19:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ret.size() < 20 && (i < v1.size() || j < v2.size())){
                               ~~^~~~~~~~~~~
jumps.cpp:19:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ret.size() < 20 && (i < v1.size() || j < v2.size())){
                                                ~~^~~~~~~~~~~
jumps.cpp:20:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i == v1.size())
            ~~^~~~~~~~~~~~
jumps.cpp:22:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         else if(j == v2.size())
                 ~~^~~~~~~~~~~~
jumps.cpp: In function 'll solve(ll, ll)':
jumps.cpp:58:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i1 = 0; i1 < v.size(); ++i1)
                    ~~~^~~~~~~~~~
jumps.cpp:59:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(ll i2 = i1+1; i2 < v.size(); ++i2)
                           ~~~^~~~~~~~~~
jumps.cpp:60:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(ll i3 = i2+1; i3 < v.size(); ++i3)
                               ~~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47360 KB Output is correct
2 Correct 37 ms 47344 KB Output is correct
3 Correct 34 ms 47360 KB Output is correct
4 Correct 36 ms 47360 KB Output is correct
5 Correct 33 ms 47360 KB Output is correct
6 Correct 32 ms 47360 KB Output is correct
7 Incorrect 33 ms 47360 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47360 KB Output is correct
2 Correct 37 ms 47344 KB Output is correct
3 Correct 34 ms 47360 KB Output is correct
4 Correct 36 ms 47360 KB Output is correct
5 Correct 33 ms 47360 KB Output is correct
6 Correct 32 ms 47360 KB Output is correct
7 Incorrect 33 ms 47360 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 80888 KB Output is correct
2 Correct 252 ms 81036 KB Output is correct
3 Correct 243 ms 80892 KB Output is correct
4 Correct 254 ms 80924 KB Output is correct
5 Correct 277 ms 80888 KB Output is correct
6 Incorrect 225 ms 80892 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47360 KB Output is correct
2 Correct 37 ms 47344 KB Output is correct
3 Correct 34 ms 47360 KB Output is correct
4 Correct 36 ms 47360 KB Output is correct
5 Correct 33 ms 47360 KB Output is correct
6 Correct 32 ms 47360 KB Output is correct
7 Incorrect 33 ms 47360 KB Output isn't correct
8 Halted 0 ms 0 KB -