제출 #698030

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
698030		winthemcut3	Global Warming (CEOI18_glo)	C++14	10 / 100	132 ms	16096 KiB

glo

#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define int ll
#define PB push_back
#define ALL(v) (v).begin(), (v).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define fi   first
#define se   second
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;

/** END OF TEMPLATE **/

const int mxN = 2e5 + 5;
int n, d;
int f1[mxN], f2[mxN], a[mxN], b[mxN];
struct fenwick {
    vector<int> bit;
    fenwick(int t) { bit.resize(t + 1, 0); }
    void update(int id, int val) {
        for(; id <= 2*n; id += id&-id) bit[id] = max(bit[id], val);
    }
    ll get(int id) {
        int temp = 0;
        for(; id > 0; id -= id&-id) temp = max(temp, bit[id]);
        return temp;
    }
};

signed main()
{
    FastIO;
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    cin >> n >> d;
    vector<int> t;
    FOR(i, 1, n) {
        cin >> a[i];
        t.PB(a[i]); t.PB(a[i] + d);
    }
    sort(ALL(t));
    FOR(i, 1, n)
        a[i] = lower_bound(ALL(t), a[i]) - t.begin() + 1,
        b[i] = lower_bound(ALL(t), a[i] + d) - t.begin() + 1;

    fenwick T1(2*n+1);
    FOR(i, 1, n) {
        f1[i] = T1.get(a[i]-1) + 1;
        T1.update(a[i], f1[i]);
    }
    fenwick T(2*n+1);
    FOR(i, 1, n) {
        f2[i] = T.get(b[i] - 1) + 1;
        T.update(a[i], f1[i]);
        T.update(b[i], f2[i]);
    }
    int res = 0;
    FOR(i, 1, n)
        res = max(res, max(f1[i], f2[i]));
    cout << res;

    return 0;
}

/*

*/

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