Submission #70964

#	Time	Username	Problem	Language	Result	Execution time	Memory
70964		MatheusLealV	Global Warming (CEOI18_glo)	C++17	100 / 100	1000 ms	171020 KiB

glo

#include <bits/stdc++.h>
#define N 200050
#define limite (1000000005)
#define mid ((a + b)/2)
using namespace std;

int n, v[N], dp[N][2], x, resp;

struct node
{
    int val;

    node *l, *r;

    node()
    {
        val = 0;

        l = r = NULL;
    }
};

node *root = new node(), *root1 = new node();

void upd(node *root, int a, int b, int i, int x)
{
    if(a == b)
    {
        root->val = max(root->val, x);

        return;
    }

    if(i <= mid)
    {
        if(!root->l) root->l = new node();

        upd(root->l, a, mid, i, x);
    }

    else
    {
        if(!root->r) root->r = new node();

        upd(root->r, mid + 1, b, i, x);
    }

    root->val = max( (root->l ? root->l->val : 0), (root->r ? root->r->val : 0) );
}

int query(node *root, int a, int b, int i, int j)
{
    if(!root or (j < a or i > b)) return 0;

    if(i <= a and j >= b) return root->val;

    return max(query(root->l, a, mid, i, j), query(root->r, mid + 1, b, i, j));
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    cin>>n>>x;

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

    for(int i = 1; i <= n; i++)
    {
        int A = query(root1, 0, limite, 0, v[i] - 1), B = query(root, 0, limite, 0, v[i] - 1);

        int C = query(root1, 0, limite, v[i], v[i] + x - 1);

        dp[i][1] = A + 1;

        dp[i][0] = max({A, B, C}) + 1;

        resp = max({resp, dp[i][0], dp[i][1]});

        upd(root, 0, limite, v[i], dp[i][0]);

        upd(root1, 0, limite, v[i], dp[i][1]);
    }

    cout<<resp<<"\n";
}

• 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