oj.uz

Submission #236829

# Submission time Handle Problem Language Result Execution time Memory
236829 2020-06-03T13:59:17 Z egekabas Triple Jump (JOI19_jumps) C++14
0 / 100
 240 ms 68856 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<int, int>    pii;
typedef pair<ull, ull>    pull;
typedef pair<ld, ld>  pld;
int sfunc(pii a, pii b){
    return a.ss < b.ss;
}
vector<pii> merge(vector<pii> v1, vector<pii> v2){
    vector<pii> ret;
    int 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;
}
int a[500009];
vector<pii> seg[2000000];
void build(int v, int tl, int 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(int v, int tl, int tr, int l, int r){
    if(tr < l || tl > r)
        return {};
    else if(l <= tl && tr <= r)
        return seg[v];
    else{
        int tm = (tl+tr)/2;
        return merge(get(2*v, tl, tm, l, r), get(2*v+1, tm+1, tr, l, r));
    }
}
int n;
int q;
int solve(int l, int r){
    vector<pii> v = get(1, 0, n-1, l, r);
    int ans = 0;
    sort(v.begin(), v.end(), sfunc);
    for(int i1 = 0; i1 < v.size(); ++i1)
        for(int i2 = i1+1; i2 < v.size(); ++i2)
            for(int 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(int i = 0; i < n; ++i)
        cin >> a[i];
    build(1, 0, n-1);
    cin >> q;
    while(q--){
        int l, r;
        cin >> l >> r;
        cout << solve(l-1, r-1) << '\n';
    }
}

Compilation message

jumps.cpp: In function 'std::vector<std::pair<int, int> > merge(std::vector<std::pair<int, int> >, std::vector<std::pair<int, 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 'int solve(int, int)':
jumps.cpp:58:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i1 = 0; i1 < v.size(); ++i1)
                     ~~~^~~~~~~~~~
jumps.cpp:59:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i2 = i1+1; i2 < v.size(); ++i2)
                            ~~~^~~~~~~~~~
jumps.cpp:60:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i3 = i2+1; i3 < v.size(); ++i3)
                                ~~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47232 KB Output is correct
2 Correct 35 ms 47360 KB Output is correct
3 Correct 35 ms 47360 KB Output is correct
4 Correct 32 ms 47360 KB Output is correct
5 Correct 33 ms 47360 KB Output is correct
6 Correct 32 ms 47352 KB Output is correct
7 Incorrect 33 ms 47392 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47232 KB Output is correct
2 Correct 35 ms 47360 KB Output is correct
3 Correct 35 ms 47360 KB Output is correct
4 Correct 32 ms 47360 KB Output is correct
5 Correct 33 ms 47360 KB Output is correct
6 Correct 32 ms 47352 KB Output is correct
7 Incorrect 33 ms 47392 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 68856 KB Output is correct
2 Correct 231 ms 68728 KB Output is correct
3 Correct 232 ms 68856 KB Output is correct
4 Correct 239 ms 68828 KB Output is correct
5 Correct 239 ms 68856 KB Output is correct
6 Incorrect 210 ms 68856 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47232 KB Output is correct
2 Correct 35 ms 47360 KB Output is correct
3 Correct 35 ms 47360 KB Output is correct
4 Correct 32 ms 47360 KB Output is correct
5 Correct 33 ms 47360 KB Output is correct
6 Correct 32 ms 47352 KB Output is correct
7 Incorrect 33 ms 47392 KB Output isn't correct
8 Halted 0 ms 0 KB -