Submission #870773

#	Time	Username	Problem	Language	Result	Execution time	Memory
870773		Darren0724	Global Warming (CEOI18_glo)	C++17	100 / 100	118 ms	13776 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define LCBorz                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);
#define int long long
#define all(x) x.begin(), x.end()
#define x first
#define y second
const int N=400005;
struct BIT{
    vector<int> v=vector<int>(N);
    void add(int p,int x){
        for(int i=p;i<N;i+=i&(-i)){
            v[i]=max(v[i],x);
        }
    }
    int ask(int p){
        int ans=0;
        for(int i=p;i>0;i-=i&(-i)){
            ans=max(ans,v[i]);
        }
        return ans;
    }
};
int32_t main() {
    LCBorz;
    int n,x;cin>>n>>x;
    vector<int> v(n);
    vector<int> t;
    for(int i=0;i<n;i++){
        cin>>v[i];
        t.push_back(v[i]);
        t.push_back(v[i]+x);
    }
    sort(all(t));
    t.resize(unique(all(t))-t.begin());
    BIT b1,b2;
    int ans=0;
    for(int i=0;i<n;i++){
        int a1=lower_bound(all(t),v[i])-t.begin()+1;
        int a2=lower_bound(all(t),v[i]+x)-t.begin()+1;
        int t1=b1.ask(a1-1);
        int t2=max(b1.ask(a2-1),b2.ask(a2-1));
        b1.add(a1,t1+1);
        b2.add(a2,t2+1);
        ans=max(ans,t1+1);
        ans=max(ans,t2+1);
    }
    cout<<ans<<endl;

    
 
    return 0;
}

• 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