oj.uz

Submission #1072697

# Submission time Handle Problem Language Result Execution time Memory
1072697 2024-08-24T02:59:01 Z boyliguanhan Global Warming (CEOI18_glo) C++17
28 / 100
 2000 ms 150580 KB 
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
struct {
    __gnu_pbds::gp_hash_table<int,int>mp;
    int query(int pos){
        int ans=0;
        while(pos)
            ans=max(ans,mp[pos]),
            pos-=pos&-pos;
        return ans;
    }
    void upd(long long 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2392 KB Output is correct
7 Correct 0 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 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 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2392 KB Output is correct
7 Correct 0 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 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 2396 KB Output is correct
14 Correct 1 ms 2512 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2392 KB Output is correct
7 Correct 0 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 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 2396 KB Output is correct
14 Correct 1 ms 2512 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 154 ms 3664 KB Output is correct
20 Correct 163 ms 3724 KB Output is correct
21 Correct 157 ms 3548 KB Output is correct
22 Correct 160 ms 3656 KB Output is correct
23 Correct 88 ms 3096 KB Output is correct
24 Correct 89 ms 3088 KB Output is correct
25 Correct 3 ms 2392 KB Output is correct
26 Correct 3 ms 2396 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2091 ms 150580 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 2062 ms 39476 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 2015 ms 88852 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2392 KB Output is correct
7 Correct 0 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 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 2396 KB Output is correct
14 Correct 1 ms 2512 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 154 ms 3664 KB Output is correct
20 Correct 163 ms 3724 KB Output is correct
21 Correct 157 ms 3548 KB Output is correct
22 Correct 160 ms 3656 KB Output is correct
23 Correct 88 ms 3096 KB Output is correct
24 Correct 89 ms 3088 KB Output is correct
25 Correct 3 ms 2392 KB Output is correct
26 Correct 3 ms 2396 KB Output is correct
27 Execution timed out 2091 ms 150580 KB Time limit exceeded
28 Halted 0 ms 0 KB -