oj.uz

Submission #616052

# Submission time Handle Problem Language Result Execution time Memory
616052 2022-07-31T19:18:05 Z Ahmadsm2005 Triple Jump (JOI19_jumps) C++17
5 / 100
 4000 ms 33744 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N,Q,A[500000],L,R,ANS[500000];
int S1[2000000],S2[2000000],S3[2000000];
vector<pair<int,int>>PA[500000];
void upd(int T,int v,int LL = 0,int RR = 500000,int idx = 0){
    if(LL == RR && LL == T){
        S1[idx] = max(v,S1[idx]);
        S2[idx] = A[T];
        S3[idx] = S1[idx] + A[T];
        return;
    }
    else if(LL > T || RR < T)return;
    upd(T,v,LL,(LL+RR)/2,idx*2+1),upd(T,v,(LL+RR)/2+1,RR,idx*2+2);
    S3[idx] = max({S3[idx*2+1],S3[idx*2+2],S1[idx*2+1] + S2[idx*2+2]});
    S1[idx] = max(S1[idx*2+1],S1[idx*2+2]);
    S2[idx] = max(S2[idx*2+1],S2[idx*2+2]);
}
int query(int L,int R,int LL=0,int RR=500000,int idx=0){
    if(RR <= R && LL >= L){
        return S3[idx];
    }
    else if(LL > R || RR < L)return (int)-3e8;
    return max(query(L,R,LL,(LL+RR)/2,idx*2+1),query(L,R,(LL+RR)/2+1,RR,idx*2+2));
}
void CALC(){
    stack<pair<int,int>>F;
    for(int i = 0; i < N; i += 1){
        while(F.size()){
            pair<int,int>TOP = F.top();
            PA[TOP.second].push_back({i, i * 2 - TOP.second});
            if(TOP.first > A[i])break;
            F.pop();
        }
        F.push({A[i],i});
    }
}
int32_t main()
{
    cin.tie(0),iostream::sync_with_stdio(0);
    cin>>N;
    for(int i = 0; i < N; i += 1){
        cin>>A[i];
        upd(i,0);
    }
    CALC();
    cin>>Q;
    vector<array<int,3>>STO;
    for(int i = 0; i < Q; i += 1){
        cin>>L>>R,L--,R--;
        STO.push_back({L,R,i});
    }
    int LST = N;
    sort(STO.rbegin(),STO.rend());
    for(int i = 0; i < Q; i += 1){
        while(LST > STO[i][0]){
            LST--;
            for(int l = 0; l < PA[LST].size();l++){
                for(int z = PA[LST][l].second; z < 5000; z++)
                upd(z,A[PA[LST][l].first] + A[LST]);
            }
        }
        //cout<<STO[i][1]<<endl;
        ANS[STO[i][2]] = query(STO[i][0],STO[i][1]);
    }
    for(int i = 0; i < Q; i += 1)cout<<ANS[i]<<'\n';
}

Compilation message

jumps.cpp: In function 'int32_t main()':
jumps.cpp:59:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             for(int l = 0; l < PA[LST].size();l++){
      |                            ~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12372 KB Output is correct
2 Correct 203 ms 12476 KB Output is correct
3 Correct 107 ms 12480 KB Output is correct
4 Correct 108 ms 12372 KB Output is correct
5 Correct 246 ms 12480 KB Output is correct
6 Correct 198 ms 12480 KB Output is correct
7 Correct 201 ms 12372 KB Output is correct
8 Correct 207 ms 12372 KB Output is correct
9 Correct 205 ms 12492 KB Output is correct
10 Correct 201 ms 12468 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12372 KB Output is correct
2 Correct 203 ms 12476 KB Output is correct
3 Correct 107 ms 12480 KB Output is correct
4 Correct 108 ms 12372 KB Output is correct
5 Correct 246 ms 12480 KB Output is correct
6 Correct 198 ms 12480 KB Output is correct
7 Correct 201 ms 12372 KB Output is correct
8 Correct 207 ms 12372 KB Output is correct
9 Correct 205 ms 12492 KB Output is correct
10 Correct 201 ms 12468 KB Output is correct
11 Execution timed out 4035 ms 28476 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4070 ms 33744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12372 KB Output is correct
2 Correct 203 ms 12476 KB Output is correct
3 Correct 107 ms 12480 KB Output is correct
4 Correct 108 ms 12372 KB Output is correct
5 Correct 246 ms 12480 KB Output is correct
6 Correct 198 ms 12480 KB Output is correct
7 Correct 201 ms 12372 KB Output is correct
8 Correct 207 ms 12372 KB Output is correct
9 Correct 205 ms 12492 KB Output is correct
10 Correct 201 ms 12468 KB Output is correct
11 Execution timed out 4035 ms 28476 KB Time limit exceeded
12 Halted 0 ms 0 KB -