Submission #1186961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186961		Born_To_Laugh	Global Warming (CEOI18_glo)	C++17	0 / 100	295 ms	34720 KiB

glo

// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(sth) sth.begin(), sth.end()
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;
#define int ll
class Segment_Tree
{
  private:
    struct node {
        int val = 0;
        int Lazy = 0;
    };
    int n;
    vector<node> Tree;
    inline void Operate(int id, int l, int r) {
        if (Tree[id].Lazy == 0)
            return;
        Tree[id].val += Tree[id].Lazy;
        if (l != r) {
            Tree[id << 1].Lazy += Tree[id].Lazy;
            Tree[id << 1 | 1].Lazy += Tree[id].Lazy;
        }
        Tree[id].Lazy = 0;
    }
    inline void Range_Update(int id, int l, int r, int lo, int hi, int num) {
        Operate(id, l, r);
        if (l > hi || r < lo)
            return;
        else if (l >= lo && r <= hi) {
            Tree[id].Lazy += num;
            Operate(id, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        Range_Update(id << 1, l, mid, lo, hi, num);
        Range_Update(id << 1 | 1, mid + 1, r, lo, hi, num);
        //
        Tree[id].val = max(Tree[id << 1].val, Tree[id << 1 | 1].val);
    }
    inline int Get(int id, int l, int r, int lo, int hi) {
        Operate(id, l, r);
        //
        if (l > hi || r < lo)
            return -INF;
        else if (l >= lo && r <= hi) {
            return Tree[id].val;
        }
        int mid = (l + r) >> 1;
        int ans1 = Get(id << 1, l, mid, lo, hi);
        int ans2 = Get(id << 1 | 1, mid + 1, r, lo, hi);
        //
        return max(ans1, ans2);
    }

  public:
    Segment_Tree(int len) {
        //
        n = len;
        Tree.assign(n << 2, {0, 0});
    }
    void Range_Update(int l, int r, int num) {
        Range_Update(1, 1, n, l, r, num);
    }
    int Get(int l, int r) {
        return Get(1, 1, n, l, r);
    }
};
void solve(){
    int n, x;cin >> n >> x;
    vector<int> a(n+1, 0);
    for(int i=1; i<=n; ++i)cin >> a[i];

    vector<int> temp;
    for(int i=1; i<=n; ++i){
        temp.push_back(a[i] + 1);
        temp.push_back(a[i] + 1 - x);
        temp.push_back(a[i]);
    }
    temp.push_back(INF);

    sort(alle(temp));
    temp.erase(unique(alle(temp)), temp.end());
    auto get_pos = [&](int x){
        int pos = upper_bound(alle(temp), x) - temp.begin();
        return pos;
    };
    
    // for(auto &elm: temp)cout << elm << ' ';
    // cout << '\n';
    // cout << get_pos(12);
    // return;

    vector<int> dp;
    vector<int> lis(n+10, 0);
    for(int i=1; i<=n; ++i){
        int pos = upper_bound(alle(dp), a[i]) - dp.begin();
        if(pos == dp.size()){
            dp.push_back(a[i]);
            lis[i] = pos;
        }
        else{
            dp[pos] = a[i];
            lis[i] = pos;
        }
    }
    // for(int i=1; i<=n; ++i)cout << lis[i] << '\n';
    Segment_Tree seg(temp.size() + 10);
    vector<int> suff(n+10, 0);
    int INFpos = get_pos(INF);
    for(int i=n; i>0; --i){
        suff[i] = seg.Get(get_pos(a[i] + 1 - x), INFpos);
        seg.Range_Update(get_pos(a[i]), get_pos(a[i]), seg.Get(get_pos(a[i] + 1), INFpos) + 1);
    }
    int ans = -INF;
    for(int i=1; i<=n; ++i){
        ans = max(ans, lis[i] + suff[i]);
    }
    cout << ans << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25