Submission #1259359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259359		minhpk	Global Warming (CEOI18_glo)	C++20	27 / 100	106 ms	8392 KiB

glo

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
int z[1000005];
vector <int> v;
int n;
struct BIT{
      int bit[1000005]={0};
      void update(int i,int val){
           i++;
           while (i<=n+64){
                bit[i]=max(bit[i],val);
                i+=i&-i;
           }
      }
      int query(int i){
           i++;
           int res=0;
           while (i>0){
               res=max(res,bit[i]);
               i-=i&-i;
           }
           return res;
      }
};
BIT f,f1;
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    for (int i=1;i<=a;i++){
         cin >> z[i];
         v.push_back(z[i]);
         v.push_back(z[i]-b);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
     n=v.size()+3;
    for (int i=1;i<=a;i++){
         int x=lower_bound(v.begin(),v.end(),z[i])-v.begin()+1;
         int y=lower_bound(v.begin(),v.end(),z[i]-b)-v.begin()+1;
         int l1=f.query(y-1)+1;
         f.update(y,l1);
         int l2=max(f.query(x-1),f1.query(x-1))+1;
         f1.update(x,l2);
    }
    cout << max(f.query(n),f1.query(n)) << "\n";
    return 0;
}

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