oj.uz

Submission #920145

# Submission time Handle Problem Language Result Execution time Memory
920145 2024-02-02T06:21:54 Z UmairAhmadMirza Global Warming (CEOI18_glo) C++17
62 / 100
 80 ms 10972 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int const N=200005;
int pre[N],suf[N];
int pre_val[N],suf_val[N];
void LIS(int arr[],int n){
    vector<int> v;
    v.push_back(arr[0]);
    pre[1]=1;
    pre_val[1]=arr[0];
    for(int i=1;i<n;i++){
        auto p=lower_bound(v.begin(),v.end(),arr[i]);
        if(p==v.end())
            v.push_back(arr[i]);
        else
            v[p-v.begin()]=arr[i];
        pre_val[i+1]=v.back();
        pre[i+1]=v.size();
    }
}
int ans=0;
void LIS_SUF(int arr[],int n,int x){
    vector<int> v;
    v.push_back(-arr[n-1]);
    for(int i=n-2;i>=0;i--){
        int pp=lower_bound(v.begin(),v.end(),-(pre_val[i+1]-x))-v.begin();
        // cout<<pre_val[i+1]<<' '<<pp<<endl;
        // for(auto j:v)
        //     cout<<j<<' ';
        // cout<<endl;
        ans=max(pre[i+1]+pp,ans);
        auto p=lower_bound(v.begin(),v.end(),-arr[i]);
        if(p==v.end())
            v.push_back(-arr[i]);
        else
            v[p-v.begin()]=-arr[i];
    }
    // cout<<endl;
}
signed main(){
    int n,x;
    cin>>n>>x;
    int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    LIS(arr,n);
    if(x==0){
        cout<<pre[n]<<endl;
        return 0;
    }
    LIS_SUF(arr,n,x);
    cout<<max(ans,pre[n])<<endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 1 ms 2392 KB Output is correct
18 Correct 1 ms 2392 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 1 ms 2392 KB Output is correct
18 Correct 1 ms 2392 KB Output is correct
19 Correct 1 ms 2392 KB Output is correct
20 Incorrect 1 ms 2392 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 9552 KB Output is correct
2 Correct 68 ms 9388 KB Output is correct
3 Correct 66 ms 9552 KB Output is correct
4 Correct 66 ms 9512 KB Output is correct
5 Correct 45 ms 9636 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3672 KB Output is correct
2 Correct 19 ms 3612 KB Output is correct
3 Correct 20 ms 3756 KB Output is correct
4 Correct 13 ms 3856 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 15 ms 4104 KB Output is correct
7 Correct 18 ms 3672 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 6992 KB Output is correct
2 Correct 39 ms 6996 KB Output is correct
3 Correct 80 ms 9556 KB Output is correct
4 Correct 54 ms 10420 KB Output is correct
5 Correct 25 ms 7496 KB Output is correct
6 Correct 49 ms 10352 KB Output is correct
7 Correct 69 ms 10972 KB Output is correct
8 Correct 37 ms 6992 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 1 ms 2392 KB Output is correct
18 Correct 1 ms 2392 KB Output is correct
19 Correct 1 ms 2392 KB Output is correct
20 Incorrect 1 ms 2392 KB Output isn't correct
21 Halted 0 ms 0 KB -