Submission #88465

#	Time	Username	Problem	Language	Result	Execution time	Memory
88465		tieunhi	Global Warming (CEOI18_glo)	C++14	100 / 100	205 ms	14668 KiB

glo

#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define N 200005
#define maxc 1ll*100000000000000007
#define ll long long

using namespace std;

int n, d, a[N], b[N], rr[N*2], cur, rig[N];
struct BIT
{
    int t[N*2];
    void reset()
    {
        memset(t, 0, sizeof t);
    }
    void upd(int x, int val)
    {
        for (; x < N*2; x += (x & -x)) t[x] = max(t[x], val);
    }
    int get(int x)
    {
        int ans = 0;
        for (; x; x -= (x & -x)) ans = max(ans, t[x]);
        return ans;
    }
}t;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> n >> d;
    FOR(i, 1, n)
    {
        cin >> a[i];
        rr[++cur] = a[i];
        rr[++cur] = a[i] + d;
    }
    sort(rr+1, rr+cur+1);
    cur = unique(rr+1, rr+cur+1) - rr - 1;
    FOR(i, 1, n)
    {
        b[i] = lower_bound(rr+1, rr+cur+1, a[i]+d) - rr;
        a[i] = lower_bound(rr+1, rr+cur+1, a[i]) - rr;
    }
    FORD(i, n, 1)
    {
        rig[i] = t.get(cur - b[i]) + 1;
        t.upd(cur - b[i] + 1, rig[i]);
    }
    int res = rig[1];
    t.reset();
    FOR(i, 1, n)
    {
        res = max(res, t.get(b[i]-1) + rig[i]);
        int valLIS = t.get(a[i]-1) + 1;
        t.upd(a[i], valLIS);
    }
    cout <<res;
}

• 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