Submission #930615

#	Time	Username	Problem	Language	Result	Execution time	Memory
930615		Sam86_b	Global Warming (CEOI18_glo)	C++17	100 / 100	137 ms	6132 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<'\n'
#define dbgv(v) cout<<#v<<" = "; for(auto x : v) cout<<x<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) #x<<'='<<(x)<<' '
#define sep cout<<"---------------"<<endl
#define kill(x) {cout<<x<<'\n'; return;}
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define sz(x) int(x.size())
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first


//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

const int N = 2e5+5;
int n, x, a[N], b[N], lis_pre[N], lis_suf[N], fen[2][N];
vector<int> temp;

void add(int l, int x, int t){
    while(l <= sz(temp)) maxm(fen[t][l], x), l += (l & -l);
}
int get(int r, int t){
    int res = 0;
    while(r <= sz(temp) and r > 0) maxm(res, fen[t][r]), r -= (r & -r);
    return res;
}

void Solve(){
    cin >> n >> x;
    f(i, 0, n) cin >> a[i], temp.pb(a[i]), b[i] = a[i];
    sort(all(temp));
    temp.resize(unique(all(temp)) - temp.begin());
    f(i, 0, n) a[i] = lower_bound(all(temp), a[i]) - temp.begin() + 1;
    f(i, 0, n) lis_pre[i] = get(a[i]-1, 0) + 1, add(a[i], lis_pre[i], 0);
    f_(i, n-1, 0){
        int t1 = a[i] + 1;
        lis_suf[i] = get(sz(temp) + 1 - t1, 1) + 1, add(sz(temp) + 1 - a[i], lis_suf[i], 1);
    }
    int ans = 0;
    f(i, 1, sz(temp)+1) fen[0][i] = fen[1][i] = 0;
    f_(i, n-1, 0){
        int t1 = b[i] - x;
        int p = upper_bound(all(temp), t1) - temp.begin() + 1;
        if(p <= n) maxm(ans, lis_pre[i] + get(sz(temp) + 1 - p, 1));
        add(sz(temp) + 1 - a[i], lis_suf[i], 1);
    }
    f(i, 0, n){
        int t1 = b[i] + x;
        int p = lower_bound(all(temp), t1) - temp.begin();
        if(p) maxm(ans, lis_suf[i] + get(p, 0));
        add(a[i], lis_pre[i], 0);
    }
    cout<<ans<<'\n';
}

int main(){
    ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int tt;
    //cin >> tt;

    tt = 1;
    while(tt--){
        Solve();
    }
}

• 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