Submission #163780

#	Time	Username	Problem	Language	Result	Execution time	Memory
163780		Alexa2001	Global Warming (CEOI18_glo)	C++17	100 / 100	231 ms	7076 KiB

glo

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2e5 + 5;

pair<int,int> a[Nmax];
int A[Nmax];
int dp1[Nmax], dp2[Nmax];
int X, n;

class AIB 
{
    int b[Nmax];

    int query(int p)
    {
        int ans = 0;
        for(; p<=n; p+=ub(p))
            ans = max(ans, b[p]);
        return ans;
    }

    void update(int p, int val)
    {
        for(; p; p-=ub(p)) b[p] = max(b[p], val);
    }
    
    int ub(int x) { return (x&(-x)); }

public:
    void clear()
    {
        memset(b, 0, sizeof(b));
    }
    
    int query_greater(int x)
    {
        int p = lower_bound(a+1, a+n+1, make_pair(x+1, 0)) - a;
        return query(p);
    }

    void update_greater(int x, int val)
    {
        int p = lower_bound(a+1, a+n+1, make_pair(x, 0)) - a;
        update(p, val);
    }

    int query_smaller(int x)
    {
        int p = lower_bound(a+1, a+n+1, make_pair(x, 0)) - a - 1;
        return query(n + 1 - p);
    }

    void update_smaller(int x, int val)
    {
        int p = lower_bound(a+1, a+n+1, make_pair(x, 0)) - a;
        update(n+1-p, val);
    }
} aib;

void norm()
{
    int i;
    for(i=1; i<=n; ++i)
        a[i] = {A[i], i};

    sort(a+1, a+n+1);
}

void solve()
{
    int i;

    aib.clear();
    for(i=n; i; --i)
    {
        dp2[i] = aib.query_greater(A[i]) + 1;
        aib.update_greater(A[i], dp2[i]);
    }
    
    int ans = 0;
    aib.clear();
    for(i=1; i<=n; ++i)
    {
        int curr_ans = aib.query_smaller(A[i] + X) + dp2[i];
        ans = max(ans, curr_ans);

        dp1[i] = aib.query_smaller(A[i]) + 1;
        aib.update_smaller(A[i], dp1[i]);
    }
    
    cout << ans << '\n';
}

int main()
{
   // freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    cin >> n >> X;

    int i;
    for(i=1; i<=n; ++i) cin >> A[i];

    norm();
    solve();

    return 0;
}

• 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