VOLIS - Dãy con không giảm dài nhất

Tác giả: ladpro98

Ngôn ngữ: C++

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define ii pair<int, int>
#define iii pair<int, ii>
#define X first
#define Y second
const int N = 1010;
using namespace std;
int bit[N * N], c[N * N];
int a[N][2];
int n, D, v;
vector<iii> b;

void Upd(int i, int val)
    {for(; i <= v; i += i & -i) bit[i] = max(bit[i], val);}
int Get(int i) 
    {int s = 0; for(; i; i -= i & -i) s = max(s, bit[i]); return s;}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> D;
    for(int i = 1; i <= n; i++) {
        cin >> v;
        a[i][1] = v - D;
        a[i][2] = v + D;
        b.push_back(iii(a[i][1], ii(i, 1)));
        b.push_back(iii(a[i][2], ii(i, 2)));
    }
    sort(b.begin(), b.end());
    v = 0;
    for(int i = 0; i < b.size(); i++) {
        if (i == 0 || b[i].X != b[i - 1].X) v++;
        a[b[i].Y.X][b[i].Y.Y] = v;
    }
    int m = 0;
    for(int i = 1; i <= n; i++)
        for(int j = a[i][2]; j >= a[i][1]; j--)
            c[++m] = j;
    int res = 0, F;
    for(int i = 1; i <= m; i++) {
        F = Get(c[i]) + 1;
        Upd(c[i], F);
        res = max(res, F);
    }
    cout << res;
    return 0;
}

Download