Submission #1072712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072712		boyliguanhan	Global Warming (CEOI18_glo)	C++17	100 / 100	46 ms	5456 KiB

glo

#include<bits/stdc++.h>
using namespace std;
int goleft[200100], goright[200100],vl[200100],pos[200100];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,x;
    cin>>n>>x;
    for(auto&i:pos)i=2e9;
    pos[0]=0;
    for(int i=1;i<=n;i++)
        cin>>vl[i];
    for(int i=n;i;i--){
        goright[i]=lower_bound(pos,pos+n+1,1e9-vl[i])-pos;
        pos[goright[i]] = 1e9-vl[i];
    }
    int ans=0;
    for(auto&i:pos)i=2e9;
    int A=clock();
    pos[0]=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,goright[i]+(int)(lower_bound(pos,pos+n+1,vl[i]+x)-pos)-1);
        goleft[i]=lower_bound(pos,pos+n+1,vl[i])-pos;
        pos[goleft[i]] = vl[i];
    }
    int B=clock();
    // cerr<<(B-A )/ 1e6<<'\n';
    cout<<ans<<'\n';
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:18:9: warning: unused variable 'A' [-Wunused-variable]
   18 |     int A=clock();
      |         ^
glo.cpp:25:9: warning: unused variable 'B' [-Wunused-variable]
   25 |     int B=clock();
      |         ^

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25