Submission #953436

#	Time	Username	Problem	Language	Result	Execution time	Memory
953436		Rifal	Global Warming (CEOI18_glo)	C++14	100 / 100	1809 ms	89684 KiB

glo

#include <bits/stdc++.h>
#include <fstream>
#define endl '\n'
#define mod 1000000007
#define INF 1000000000
#define INF2 2000000000
///#define cin fin
///#define cout fout
using namespace std;
double const EPS = 1e-14;
typedef long long ll;
///ofstream fout("herding.out");
///ifstream fin("herding.in");
const int M = 6e5 + 3;
const int N = 6e5 + 5;
ll seg[N*4];
map<ll,int> mp;
void Build(int x, int l, int r) {
    if(l == r) {
        seg[x] = 0;
    }
    else {
        int mid = (l+r)/2;
        Build(x*2,l,mid); Build(x*2+1,mid+1,r);
        seg[x] = 0;
    }
}
void Update(int x, int l, int r, int pos, ll val) {
    if(l == r) {
        seg[x] = max(seg[x],val);
    }
    else {
        int mid = (l+r)/2;
        if(pos <= mid) Update(x*2,l,mid,pos,val);
        else Update(x*2+1,mid+1,r,pos,val);
        seg[x] = max(seg[x*2],seg[x*2+1]);
    }
}
ll sol(int x, int l, int r, int L, int R) {
    if(l > R || r < L) {
        return 0;
    }
    else if(l >= L && r <= R) {
        return seg[x];
    }
    else {
        int mid = (l+r)/2;
        return max(sol(x*2,l,mid,L,R),sol(x*2+1,mid+1,r,L,R));
    }
}
int main()
{
    ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    int n; ll x; cin >> n >> x; ll arr[n+1] = {};
    set<ll> st;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
        st.insert(arr[i]);
        st.insert(arr[i]-x);
        st.insert(arr[i]+x);
    }
    ll dp1[n+1] = {}, dp2[n+1] = {};
    int cnt = 1;
    for(auto i : st) {
        mp[i] = cnt; cnt++; }
    for(int i = 1; i <= n; i++) {
        int cur = mp[arr[i]];
        ll mx = sol(1,1,M,1,cur-1);
        dp1[i] = max(dp1[i],mx+1);
        Update(1,1,M,cur,dp1[i]);
    }
    Build(1,1,M);
    for(int i = n; i >= 1; i--) {
        int cur = mp[arr[i]];
        ll mx = sol(1,1,M,cur+1,M);
        dp2[i] = max(dp2[i],mx+1);
        Update(1,1,M,cur,dp2[i]);
    }
    Build(1,1,M);
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        int cur = mp[arr[i]+x];
        int cur2 = mp[arr[i]];
        ll mx = sol(1,1,M,1,cur-1);
        ans = max(ans,dp2[i]+mx);
        Update(1,1,M,cur2,dp1[i]);
    }
    Build(1,1,M);
    for(int i = n; i >= 1; i--) {
        int cur = mp[arr[i]-x];
        int cur2 = mp[arr[i]];
        ll mx = sol(1,1,M,cur+1,M);
        ans = max(ans,mx+dp1[i]);
        Update(1,1,M,cur2,dp2[i]);
    }
    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