Submission #1049245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049245		Hamed_Ghaffari	Global Warming (CEOI18_glo)	C++17	100 / 100	230 ms	13100 KiB

glo

#include <bits/stdc++.h>
using namespace std;

using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using ull = unsigned long long;

#define X               first
#define Y               second
#define SZ(x)           int(x.size())
#define all(x)          x.begin(), x.end()
#define mins(a,b)       (a = min(a,b))
#define maxs(a,b)       (a = max(a,b))
#define pb              push_back
#define Mp              make_pair
#define lc              id<<1
#define rc              lc|1
#define mid             ((l+r)/2)
mt19937_64              rng(chrono::steady_clock::now().time_since_epoch().count());

const ll  INF = 2e9+7;
const ll  MOD = 1e9 + 7;
const int MXN = 4e5+5;
const int LOG = 23;

int n, x, a[MXN], N;
vector<int> cmp;

inline int GI(int x) {
    return lower_bound(all(cmp), x)-cmp.begin();
}

int seg[2][MXN<<2];
void Upd(int ind, int p, int x, int l=0, int r=N, int id=1) {
    if(r-l==1) {
        maxs(seg[ind][id], x);
        return;
    }
    if(p<mid) Upd(ind, p, x, l, mid, lc);
    else Upd(ind, p, x, mid, r, rc);
    seg[ind][id] = max(seg[ind][lc], seg[ind][rc]);
}
int Get(int ind, int s, int e, int l=0, int r=N, int id=1) {
    if(s<=l && r<=e) return seg[ind][id];
    if(e<=mid) return Get(ind, s, e, l, mid, lc);
    if(s>=mid) return Get(ind, s, e, mid, r, rc);
    return max(Get(ind, s, e, l, mid, lc), Get(ind, s, e, mid, r, rc));
}

void Main() {
    cin >> n >> x;
    for(int i=1; i<=n; i++) cin >> a[i];
    cmp.pb(-INF);
    for(int i=1; i<=n; i++) cmp.pb(a[i]), cmp.pb(a[i]+x);
    sort(all(cmp));
    cmp.resize(unique(all(cmp))-cmp.begin());
    N = SZ(cmp);
    for(int i=1; i<=n; i++) {
        Upd(1, GI(a[i]), max(Get(1, 0, GI(a[i])), Get(0, 0, GI(a[i]+x)))+1);
        Upd(0, GI(a[i]), Get(0, 0, GI(a[i]))+1);
    }
    cout << max(Get(0, 0, N), Get(1, 0, N)) << '\n';
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int T = 1;
    // cin >> T;
    while(T--) Main();
    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