oj.uz

Submission #1072691

# Submission time Handle Problem Language Result Execution time Memory
1072691 2024-08-24T02:56:52 Z boyliguanhan Global Warming (CEOI18_glo) C++17
0 / 100
 2000 ms 2396 KB 
#include<bits/stdc++.h>
using namespace std;
struct {
    map<int,int>mp;
    int query(int pos){
        int ans=0;
        while(pos)
            ans=max(ans,mp[pos]),
            pos-=pos&-pos;
        return ans;
    }
    void upd(int pos,int x){
        while(pos<=2e9)
            mp[pos]=max(mp[pos],x),
            pos+=pos&-pos;
    }
    void reset(){
        mp.clear();
    }  
} BIT;
int goleft[200100], goright[200100], vl[200100];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,x;
    cin>>n>>x;
    for(int i=1;i<=n;i++){ cin>>vl[i];
        goleft[i]=BIT.query(vl[i]-1)+1;
        BIT.upd(vl[i],goleft[i]);
    }
    BIT.reset();
    for(int i=n;i;i--){
        goright[i]=BIT.query(1e9-vl[i])+1;
        BIT.upd(1e9-vl[i]+1,goright[i]);
    }
    int ans=0;
    BIT.reset();
    for(int i=1;i<=n;i++){
        ans=max(ans,goright[i]+BIT.query(vl[i]+x-1));
        BIT.upd(vl[i],goleft[i]);
    }
    cout<<ans<<'\n';
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 25.0

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