oj.uz

Submission #236836

# Submission time Handle Problem Language Result Execution time Memory
236836 2020-06-03T14:22:46 Z egekabas Triple Jump (JOI19_jumps) C++14
5 / 100
 4000 ms 70908 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() < 23 && (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 n;
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 ms[2000000];
void bmax(int v, int tl, int tr){
    if(tl == tr){
        ms[v] = a[tl];
        return;
    }
    bmax(2*v, tl, (tl+tr)/2);
    bmax(2*v+1, (tl+tr)/2+1, tr);
    ms[v] = max(ms[2*v], ms[2*v+1]);
}
int gmax(int v, int tl, int tr, int l, int r){
    if(tr < l || tl > r || l > r)
        return -1e9;
    else if(l <= tl && tr <= r)
        return ms[v];
    else{
        int tm = (tl+tr)/2;
        return max(gmax(2*v, tl, tm, l, r), gmax(2*v+1, tm+1, tr, l, r));
    }
}
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){
            int val1 = gmax(1, 0, n-1, max(l, v[i1].ss-(v[i2].ss-v[i1].ss)),min(r ,v[i1].ss-1));
            int val2 = gmax(1, 0, n-1, v[i2].ss+(v[i2].ss-v[i1].ss), r-1);
            int val3 = gmax(1, 0, n-1, max(l, v[i1].ss+1), min(r, (v[i1].ss+v[i2].ss)/2));
            ans = max(ans, v[i1].ff+v[i2].ff+max({val1, val2, val3}));
        }
    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);
    bmax(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() < 23 && (i < v1.size() || j < v2.size())){
                               ~~^~~~~~~~~~~
jumps.cpp:19:50: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ret.size() < 23 && (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:79:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i1 = 0; i1 < v.size(); ++i1)
                     ~~~^~~~~~~~~~
jumps.cpp:80:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i2 = i1+1; i2 < v.size(); ++i2){
                            ~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 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 34 ms 47360 KB Output is correct
5 Correct 34 ms 47360 KB Output is correct
6 Correct 35 ms 47360 KB Output is correct
7 Correct 35 ms 47360 KB Output is correct
8 Correct 35 ms 47360 KB Output is correct
9 Correct 35 ms 47360 KB Output is correct
10 Correct 34 ms 47264 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 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 34 ms 47360 KB Output is correct
5 Correct 34 ms 47360 KB Output is correct
6 Correct 35 ms 47360 KB Output is correct
7 Correct 35 ms 47360 KB Output is correct
8 Correct 35 ms 47360 KB Output is correct
9 Correct 35 ms 47360 KB Output is correct
10 Correct 34 ms 47264 KB Output is correct
11 Execution timed out 4067 ms 48480 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 70908 KB Output is correct
2 Correct 228 ms 70904 KB Output is correct
3 Correct 228 ms 70904 KB Output is correct
4 Correct 237 ms 70904 KB Output is correct
5 Correct 235 ms 70880 KB Output is correct
6 Incorrect 204 ms 70904 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 29 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 34 ms 47360 KB Output is correct
5 Correct 34 ms 47360 KB Output is correct
6 Correct 35 ms 47360 KB Output is correct
7 Correct 35 ms 47360 KB Output is correct
8 Correct 35 ms 47360 KB Output is correct
9 Correct 35 ms 47360 KB Output is correct
10 Correct 34 ms 47264 KB Output is correct
11 Execution timed out 4067 ms 48480 KB Time limit exceeded
12 Halted 0 ms 0 KB -