제출 #1348905

#제출 시각아이디문제언어결과실행 시간메모리
1348905biankGlobal Warming (CEOI18_glo)C++20
100 / 100
97 ms5924 KiB
#include <bits/stdc++.h>
 
using namespace std;
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
 
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vb = vector<bool>;
using pll = pair<ll, ll>;

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

#define pb push_back
#define eb emplace_back
#define ef emplace_front

#define fst first
#define snd second
 
struct FTree {
    int n;
    vi ft;
    FTree(int _n) : n(_n + 9), ft(n, 0) {}
    void update(int x, int v) {
        for (++x; x < n; x += x & -x) ft[x] = max(ft[x], v);
    }
    int query(int x) {
        int m = 0;
        for (; x > 0; x -= x & -x) m = max(m, ft[x]);
        return m;
    }
};

int main() {
    ios::sync_with_stdio(0);                
    cin.tie(0); cout.tie(0);
    
    int n, x;
    cin >> n >> x;
    vi t(n);
    forn(i, n) cin >> t[i];
    
    vi values = t;
    forn(i, n) values.pb(t[i] - x);
    sort(all(values));
    values.erase(unique(all(values)), end(values));
    
    FTree dp0(sz(values)), dp1(sz(values));
    forn(i, n) {
        int pos_t = int(lower_bound(all(values), t[i]) - begin(values));
        int pos_td = int(lower_bound(all(values), t[i] - x) - begin(values));
        dp1.update(pos_t, max(dp0.query(pos_t), dp1.query(pos_t)) + 1);
        dp0.update(pos_td, dp0.query(pos_td) + 1);
    }
    
    cout << dp1.query(sz(values)) << "\n";
    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...