oj.uz

Submission #1008131

# Submission time Handle Problem Language Result Execution time Memory
1008131 2024-06-26T07:53:32 Z vjudge1 Global Warming (CEOI18_glo) C++17
100 / 100
 656 ms 56656 KB 
/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, OCaml, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=(1<<(int)log2(1000000)+1);
int Tree[N*3+1],ans[200001],ans2[200001],arr[200001];
int l,r;
map <int,int> mp;

int find(int l1,int r1,int i){
    if(l1>r||r1<l) return 0;
    if(l1>=l&&r1<=r) return Tree[i];
    int mid=(l1+r1)/2;
    return max(find(l1,mid,i*2),find(mid+1,r1,i*2+1));
} 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,x;
    cin>>n>>x;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        mp[arr[i]]++;
        mp[arr[i]+x]++;
    }
    int k=1;
    for(auto [i,j]:mp){
        mp[i]=k;
        k++;
    }
    for(int i=n-1;i>=0;i--){
        l=mp[arr[i]]+1,r=k;
        ans[i]=find(0,N-1,1)+1;
        
        int indx=mp[arr[i]]+N;
        Tree[indx]=ans[i];
        indx/=2;
        while(indx!=0){
            Tree[indx]=max(Tree[indx*2],Tree[indx*2+1]);
            indx/=2;
        }
    }
    memset(Tree,0,sizeof Tree);
    for(int i=0;i<n;i++){
        l=1,r=mp[arr[i]+x]-1;
        ans2[i]=find(0,N-1,1)+1;
        
        l=1,r=mp[arr[i]]-1;
        int num=find(0,N-1,1)+1;
        
        int indx=mp[arr[i]]+N;
        Tree[indx]=num;
        indx/=2;
        while(indx!=0){
            Tree[indx]=max(Tree[indx*2],Tree[indx*2+1]);
            indx/=2;
        }    
    }
    // for(int i=0;i<n;i++) cout<<ans[i]<<" ";
    // cout<<endl;
    // for(int i=0;i<n;i++) cout<<ans2[i]<<" ";
    int mx=0;
    for(int i=0;i<n;i++) mx=max(mx,ans[i]+ans2[i]-1);
    cout<<mx<<endl;
    
    return 0;
}

Compilation message

glo.cpp:12:35: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   12 | const int N=(1<<(int)log2(1000000)+1);
      |                 ~~~~~~~~~~~~~~~~~~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29528 KB Output is correct
2 Correct 4 ms 29532 KB Output is correct
3 Correct 4 ms 29440 KB Output is correct
4 Correct 5 ms 29528 KB Output is correct
5 Correct 6 ms 29532 KB Output is correct
6 Correct 3 ms 29532 KB Output is correct
7 Correct 3 ms 29412 KB Output is correct
8 Correct 4 ms 29528 KB Output is correct
9 Correct 5 ms 29528 KB Output is correct
10 Correct 4 ms 29424 KB Output is correct
11 Correct 4 ms 29020 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29528 KB Output is correct
2 Correct 4 ms 29532 KB Output is correct
3 Correct 4 ms 29440 KB Output is correct
4 Correct 5 ms 29528 KB Output is correct
5 Correct 6 ms 29532 KB Output is correct
6 Correct 3 ms 29532 KB Output is correct
7 Correct 3 ms 29412 KB Output is correct
8 Correct 4 ms 29528 KB Output is correct
9 Correct 5 ms 29528 KB Output is correct
10 Correct 4 ms 29424 KB Output is correct
11 Correct 4 ms 29020 KB Output is correct
12 Correct 6 ms 29020 KB Output is correct
13 Correct 4 ms 29532 KB Output is correct
14 Correct 5 ms 29068 KB Output is correct
15 Correct 4 ms 29016 KB Output is correct
16 Correct 6 ms 29020 KB Output is correct
17 Correct 5 ms 29532 KB Output is correct
18 Correct 4 ms 29532 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29528 KB Output is correct
2 Correct 4 ms 29532 KB Output is correct
3 Correct 4 ms 29440 KB Output is correct
4 Correct 5 ms 29528 KB Output is correct
5 Correct 6 ms 29532 KB Output is correct
6 Correct 3 ms 29532 KB Output is correct
7 Correct 3 ms 29412 KB Output is correct
8 Correct 4 ms 29528 KB Output is correct
9 Correct 5 ms 29528 KB Output is correct
10 Correct 4 ms 29424 KB Output is correct
11 Correct 4 ms 29020 KB Output is correct
12 Correct 6 ms 29020 KB Output is correct
13 Correct 4 ms 29532 KB Output is correct
14 Correct 5 ms 29068 KB Output is correct
15 Correct 4 ms 29016 KB Output is correct
16 Correct 6 ms 29020 KB Output is correct
17 Correct 5 ms 29532 KB Output is correct
18 Correct 4 ms 29532 KB Output is correct
19 Correct 6 ms 29276 KB Output is correct
20 Correct 7 ms 29276 KB Output is correct
21 Correct 6 ms 29260 KB Output is correct
22 Correct 5 ms 29020 KB Output is correct
23 Correct 5 ms 29260 KB Output is correct
24 Correct 5 ms 29064 KB Output is correct
25 Correct 6 ms 29020 KB Output is correct
26 Correct 7 ms 29020 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 42068 KB Output is correct
2 Correct 420 ms 42252 KB Output is correct
3 Correct 454 ms 42068 KB Output is correct
4 Correct 393 ms 42064 KB Output is correct
5 Correct 232 ms 35924 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 35412 KB Output is correct
2 Correct 111 ms 35396 KB Output is correct
3 Correct 127 ms 35440 KB Output is correct
4 Correct 66 ms 32336 KB Output is correct
5 Correct 5 ms 29408 KB Output is correct
6 Correct 71 ms 32880 KB Output is correct
7 Correct 86 ms 34548 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 41812 KB Output is correct
2 Correct 297 ms 42080 KB Output is correct
3 Correct 656 ms 54672 KB Output is correct
4 Correct 269 ms 42068 KB Output is correct
5 Correct 169 ms 41812 KB Output is correct
6 Correct 330 ms 53356 KB Output is correct
7 Correct 313 ms 53244 KB Output is correct
8 Correct 213 ms 41812 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 29528 KB Output is correct
2 Correct 4 ms 29532 KB Output is correct
3 Correct 4 ms 29440 KB Output is correct
4 Correct 5 ms 29528 KB Output is correct
5 Correct 6 ms 29532 KB Output is correct
6 Correct 3 ms 29532 KB Output is correct
7 Correct 3 ms 29412 KB Output is correct
8 Correct 4 ms 29528 KB Output is correct
9 Correct 5 ms 29528 KB Output is correct
10 Correct 4 ms 29424 KB Output is correct
11 Correct 4 ms 29020 KB Output is correct
12 Correct 6 ms 29020 KB Output is correct
13 Correct 4 ms 29532 KB Output is correct
14 Correct 5 ms 29068 KB Output is correct
15 Correct 4 ms 29016 KB Output is correct
16 Correct 6 ms 29020 KB Output is correct
17 Correct 5 ms 29532 KB Output is correct
18 Correct 4 ms 29532 KB Output is correct
19 Correct 6 ms 29276 KB Output is correct
20 Correct 7 ms 29276 KB Output is correct
21 Correct 6 ms 29260 KB Output is correct
22 Correct 5 ms 29020 KB Output is correct
23 Correct 5 ms 29260 KB Output is correct
24 Correct 5 ms 29064 KB Output is correct
25 Correct 6 ms 29020 KB Output is correct
26 Correct 7 ms 29020 KB Output is correct
27 Correct 398 ms 42068 KB Output is correct
28 Correct 420 ms 42252 KB Output is correct
29 Correct 454 ms 42068 KB Output is correct
30 Correct 393 ms 42064 KB Output is correct
31 Correct 232 ms 35924 KB Output is correct
32 Correct 98 ms 35412 KB Output is correct
33 Correct 111 ms 35396 KB Output is correct
34 Correct 127 ms 35440 KB Output is correct
35 Correct 66 ms 32336 KB Output is correct
36 Correct 5 ms 29408 KB Output is correct
37 Correct 71 ms 32880 KB Output is correct
38 Correct 86 ms 34548 KB Output is correct
39 Correct 250 ms 41812 KB Output is correct
40 Correct 297 ms 42080 KB Output is correct
41 Correct 656 ms 54672 KB Output is correct
42 Correct 269 ms 42068 KB Output is correct
43 Correct 169 ms 41812 KB Output is correct
44 Correct 330 ms 53356 KB Output is correct
45 Correct 313 ms 53244 KB Output is correct
46 Correct 213 ms 41812 KB Output is correct
47 Correct 232 ms 41812 KB Output is correct
48 Correct 230 ms 41640 KB Output is correct
49 Correct 612 ms 54772 KB Output is correct
50 Correct 248 ms 43344 KB Output is correct
51 Correct 239 ms 39504 KB Output is correct
52 Correct 335 ms 43580 KB Output is correct
53 Correct 388 ms 56144 KB Output is correct
54 Correct 379 ms 56656 KB Output is correct
55 Correct 481 ms 52564 KB Output is correct