Submission #658705

#	Time	Username	Problem	Language	Result	Execution time	Memory
658705		shrimb	Global Warming (CEOI18_glo)	C++17	100 / 100	544 ms	174404 KiB

glo

#include"bits/stdc++.h"
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;

#define int long long
#define endl '\n'
#define mod 1000000007
//\
#define mod 1686876991

const int maxa = 2000000000;
const int maxn = 200001;
const int N = exp2(ceil(log2(maxa)));

struct node {
    int Val = 0;
    node *Left = 0, *Right = 0;
};

int Left, Right, Pos, Val;

node *seg, *seg2;

int Query (int l = 1, int r = N, node *ind = seg) {
    if (!ind || l > Right || r < Left) return 0;
    if (l >= Left and r <= Right) return ind -> Val;
    int m = (l + r) / 2;
    return max(Query(l, m, ind -> Left), Query(m + 1, r, ind -> Right));
}

void Update (int l = 1, int r = N, node *ind = seg) {
    if (l > Pos || r < Pos) return;
    if (l == r) {
        ind -> Val = max(ind -> Val, Val);
        return;
    }
    int m = (l + r) / 2;
    if (Pos <= m) {
        if (!ind -> Left) ind -> Left = new node;
        Update(l, m, ind -> Left);
        ind -> Val = max(ind -> Val, ind -> Left -> Val);
    } else {
        if (!ind -> Right) ind -> Right = new node;
        Update(m + 1, r, ind -> Right);
        ind -> Val = max(ind -> Val, ind -> Right -> Val);
    }
}

signed main () {
    cin.tie(0)->sync_with_stdio(0);
    int n, x;
    cin >> n >> x;
    seg = new node;
    seg2 = new node;
    int a[n];
    for (int i = 0 ; i < n ; i++) cin >> a[i];
    int dp[2][n];
    Left = 0;
    int Ans = 0;
    for (int i = 0 ; i < n ; i++) {
        Right = a[i] - 1;
        Val = dp[0][i] = Query() + 1;
        dp[1][i] = Query(1,N,seg2)+1;
        Right = a[i] - 1 + x;
        dp[1][i] = max(dp[1][i], Query() + 1);
        Pos = a[i];
        Update();
        Val = dp[1][i];
        Update(1,N,seg2);
        Ans = max({Ans, dp[0][i], dp[1][i]});
    }
    // for (int i = 0 ; i < n ; i++) cout << dp[0][i] << " " << dp[1][i] << endl;
    cout << Ans << endl;
}

Compilation message (stderr)

glo.cpp:14:1: warning: multi-line comment [-Wcomment]
   14 | //\
      | ^

• 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