oj.uz

Submission #1096988

# Submission time Handle Problem Language Result Execution time Memory
1096988 2024-10-05T15:58:57 Z Tame Triple Jump (JOI19_jumps) C++14
19 / 100
 346 ms 147144 KB 
#include <bits/stdc++.h>
#define pu push
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define fi first
#define se second
#define el cout<<"\n"
#define ll long long
#define ld long double
#define MASK(i) (1LL<<(i))
#define BIT(x, i) (((x)>>(i))&1)
#define SET_ON(x, i) ((x)|MASK(i))
#define SET_OFF(x, i) ((x)&~MASK(i))
#define c_bit(i) __builtin_popcount(i)
const int MAX_SIZE = 500010;
const int inf = (int)1e9+7;
const ll INF = (ll)1e18;
using namespace std;

template<class T1, class T2>
    bool maximize(T1 &x, T2 y){if(x<y){x=y; return true;} return false;}
template<class T1, class T2>
    bool minimize(T1 &x, T2 y){if(x>y){x=y; return true;} return false;}

int nLength, nQuery;
int a[MAX_SIZE];

vector<pair<int,int>>queries, tmp;

struct SegmentTree{
    int n; vector<pair<int,int>>st;
    SegmentTree(int _n=0){
        n=_n; st.resize(4*n+5);
    }
    void build(int id, int l, int r){
        if (l==r){
            st[id]=make_pair(a[l], l); return;
        }
        int m = (l+r)>>1;
        build(2*id,l,m); build(2*id+1,m+1,r);
        st[id].fi = max(st[2*id].fi, st[2*id+1].fi);
        st[id].se = (st[2*id].fi>st[2*id+1].fi)?(st[2*id].se):(st[2*id+1].se);
    }
    void update(int id, int l, int r, int v, int k){
        if (r<v || v<l) return;
        if (l==r){
            st[id].fi=k; return;
        }
        int m = (l+r)>>1;
        update(2*id, l, m, v, k); update(2*id+1, m+1, r, v, k);
        st[id].fi = max(st[2*id].fi, st[2*id+1].fi);
        st[id].se = (st[2*id].fi>st[2*id+1].fi)?(st[2*id].se):(st[2*id+1].se);
    }
    pair<int,int>get(int id, int l, int r, int u, int v){
        if (r<u || v<l){
            pair<int,int>e = make_pair(-inf, -inf);
            return e;
        }
        if (l>=u && r<=v) return st[id];
        int m = (l+r)>>1;
        pair<int,int>x=get(2*id, l, m, u, v), y=get(2*id+1, m+1, r, u, v);
        if (x.fi > y.fi) return x;
        return y;
    }
};
SegmentTree IT(MAX_SIZE);

void init(){
    cin>>nLength;
    for (int i=1; i<=nLength; i++){
        cin>>a[i];
    }
    cin>>nQuery;
    for (int i=1; i<=nQuery; i++){
        int l, r; cin>>l>>r;
        queries.pb(make_pair(l, r));
    }
}

bool cmp(const pair<int,int>&x, pair<int,int>&y){
    return x.se < y.se;
}

namespace subtask1{
    bool check(){
        return max(nLength, nQuery)<=100;
    }

    ll board[105][105];

    void solve(){
        memset(board, -0x3f, sizeof(board));
        for (int i=1; i<=nLength; i++){
            for (int j=i+1; j<=nLength; j++){
                for (int k=i+1; k<j; k++){
                    if (abs(k-i) <= abs(j-k)) maximize(board[i][j], a[i]+a[j]+a[k]);
                }
            }
        }
        for (int i=0; i<(int)queries.size(); i++){
            int l=queries[i].fi, r=queries[i].se; ll ans=0;
            for (int u=l; u<=r; u++){
                for (int v=u; v<=r; v++){
                    maximize(ans, board[u][v]);
                }
            }
            cout<<ans<<"\n";
        }
    }
}

namespace subtask2{
    bool check(){
        return nLength<=5000;
    }

    int rmq[5010][15], LOG=13;
    ll dp[5003][5003];

    int getMax(int l, int r){
        int k = 31 - __builtin_clz(r-l+1);
        return max(rmq[l][k], rmq[r-MASK(k)+1][k]);
    }

    void solve(){
        for (int i=1; i<=nLength; i++) rmq[i][0] = a[i];
        for (int j=1; j<=LOG; j++){
            for (int i=1; i<=nLength; i++){
                rmq[i][j] = max(rmq[i][j-1], rmq[i+MASK(j-1)][j-1]);
            }
        }

        for (int i=1; i<=nLength; i++){
            for (int j=i+2; j<=nLength; j++){
                maximize(dp[i][j], a[i] + a[j] + getMax(i+1, (i+j)/2));
            }
        }

        for (int j=1; j<=nLength; j++){
            for (int i=j; i>=1; i--){
                if (i+1<j) maximize(dp[i][j], dp[i+1][j]);
                if (j-1>i) maximize(dp[i][j], dp[i][j-1]);
                if (i+1<j && j-1>i) maximize(dp[i][j], dp[i+1][j-1]);
            }
        }

        for (int i=0; i<(int)queries.size(); i++){
            int l=queries[i].fi, r=queries[i].se;
            cout<<dp[l][r]<<"\n";
        }
    }
}

void ilovesunshine(){
    init();

    if (subtask1::check()) return subtask1::solve();
    if (subtask2::check()) return subtask2::solve();
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ilovesunshine();
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16092 KB Output is correct
2 Correct 6 ms 16216 KB Output is correct
3 Correct 9 ms 16220 KB Output is correct
4 Correct 7 ms 16220 KB Output is correct
5 Correct 7 ms 16220 KB Output is correct
6 Correct 6 ms 16172 KB Output is correct
7 Correct 7 ms 16216 KB Output is correct
8 Correct 8 ms 16220 KB Output is correct
9 Correct 7 ms 16216 KB Output is correct
10 Correct 6 ms 16220 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16092 KB Output is correct
2 Correct 6 ms 16216 KB Output is correct
3 Correct 9 ms 16220 KB Output is correct
4 Correct 7 ms 16220 KB Output is correct
5 Correct 7 ms 16220 KB Output is correct
6 Correct 6 ms 16172 KB Output is correct
7 Correct 7 ms 16216 KB Output is correct
8 Correct 8 ms 16220 KB Output is correct
9 Correct 7 ms 16216 KB Output is correct
10 Correct 6 ms 16220 KB Output is correct
11 Correct 334 ms 146968 KB Output is correct
12 Correct 324 ms 146944 KB Output is correct
13 Correct 328 ms 146880 KB Output is correct
14 Correct 319 ms 147144 KB Output is correct
15 Correct 328 ms 147036 KB Output is correct
16 Correct 311 ms 146460 KB Output is correct
17 Correct 346 ms 146368 KB Output is correct
18 Correct 298 ms 146372 KB Output is correct
19 Correct 296 ms 146884 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 18524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16092 KB Output is correct
2 Correct 6 ms 16216 KB Output is correct
3 Correct 9 ms 16220 KB Output is correct
4 Correct 7 ms 16220 KB Output is correct
5 Correct 7 ms 16220 KB Output is correct
6 Correct 6 ms 16172 KB Output is correct
7 Correct 7 ms 16216 KB Output is correct
8 Correct 8 ms 16220 KB Output is correct
9 Correct 7 ms 16216 KB Output is correct
10 Correct 6 ms 16220 KB Output is correct
11 Correct 334 ms 146968 KB Output is correct
12 Correct 324 ms 146944 KB Output is correct
13 Correct 328 ms 146880 KB Output is correct
14 Correct 319 ms 147144 KB Output is correct
15 Correct 328 ms 147036 KB Output is correct
16 Correct 311 ms 146460 KB Output is correct
17 Correct 346 ms 146368 KB Output is correct
18 Correct 298 ms 146372 KB Output is correct
19 Correct 296 ms 146884 KB Output is correct
20 Incorrect 17 ms 18524 KB Output isn't correct
21 Halted 0 ms 0 KB -