Submission #236832

#	Time	Username	Problem	Language	Result	Execution time	Memory
236832		egekabas	Triple Jump (JOI19_jumps)	C++14	0 / 100	277 ms	81036 KiB

jumps

#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 (stderr)

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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54