oj.uz

Submission #1022483

# Submission time Handle Problem Language Result Execution time Memory
1022483 2024-07-13T14:59:02 Z handlename Global Warming (CEOI18_glo) C++17
0 / 100
 36 ms 4692 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define float long double
const int MOD=1e9+7;
// const int MOD=998244353;
const int sqn=450;
const long double eps=1e-6;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
long long power(long long a,long long b,long long p=MOD){
    long long res=1;
    while (b>0){
        if (b%2==1) res=(res*a)%p;
        b/=2;
        a=(a*a)%p;
    }
    return res;
}
long long n,x,arr[200001],ans[200001];
long long res;
void runtc(){
    cin>>n>>x;
    for (int i=1;i<=n;i++){
        cin>>arr[i];
    }
    //can consider only decrementing
    //only need consider decrement [1,x]
    //try to "fix" x
    //find LIS for prefix and suffix
    vector<long long> lol;
    for (int i=n;i>=1;i--){
        int pos=lower_bound(lol.begin(),lol.end(),-(arr[i]-x))-lol.begin();
        ans[i]=pos+1;
        pos=lower_bound(lol.begin(),lol.end(),-(arr[i]))-lol.begin();
        if (pos>=lol.size()){
            lol.pb(-arr[i]);
        }
        else {
            lol[pos]=-arr[i];
        }
    }
    lol.clear();
    for (int i=1;i<=n;i++){
        int pos=lower_bound(lol.begin(),lol.end(),arr[i])-lol.begin();
        if (pos>=lol.size()){
            lol.pb(arr[i]);
        }
        else {
            lol[pos]=arr[i];
        }
        res=max(res,(long long)pos+ans[i]-1);
    }
    cout<<res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("pcb.in","r",stdin);
    // freopen("pcb.out","w",stdout);
    //freopen("input1.in","r",stdin);
    // freopen("output1.out","w",stdout);
    //freopen("tower_rush_input.txt","r",stdin);
    //freopen("hackercup_output.txt","w",stdout);
    int tcs;
    // cin>>tcs;
    tcs=1;
    for (int i=1;i<=tcs;i++){
        // cout<<"Case #"<<i<<": ";
        runtc();
    }
}

Compilation message

glo.cpp: In function 'void runtc()':
glo.cpp:37:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         if (pos>=lol.size()){
      |             ~~~^~~~~~~~~~~~
glo.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         if (pos>=lol.size()){
      |             ~~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 25.0

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