Submission #895260

#	Time	Username	Problem	Language	Result	Execution time	Memory
895260		TheSahib	Global Warming (CEOI18_glo)	C++17	100 / 100	354 ms	35412 KiB

glo

#include <bits/stdc++.h>

#define ll long long
#define oo 1e9
#define pii pair<int, int>

using namespace std;

const int MAX = 2e5 + 5, treesize = MAX * 21, CAP = 1e9 + 9;

int n, x;
int arr[MAX];
int tree[treesize], L[treesize], R[treesize];
int LIS[MAX];

int nxt = 2;

void update(int node, int l, int r, int pos, int val){
    if(l == r){
        tree[node] = max(val, tree[node]);
        return;
    }
    int mid = (l + r) / 2;
    if(pos <= mid){
        if(!L[node]) L[node] = nxt++;
        update(L[node], l, mid, pos, val);
    }
    else{
        if(!R[node]) R[node] = nxt++;
        update(R[node], mid + 1, r, pos, val);
    }
    tree[node] = max(tree[L[node]], tree[R[node]]);
}

int ask(int node, int l, int r, int ql, int qr){
    if(!node) return 0;
    if(qr < l || r < ql) return 0;
    if(ql <= l && r <= qr) return tree[node];
    int mid = (l + r) / 2;
    return max(ask(L[node], l, mid, ql, qr), ask(R[node], mid + 1, r, ql, qr));
}

void solve(){
    cin >> n >> x;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    vector<int> v;
    for(int i = 1; i <= n; i++){
        int pos = lower_bound(v.begin(), v.end(), arr[i]) - v.begin();
        LIS[i] = pos + 1;
        if(pos == v.size()){
            v.push_back(arr[i]);
        }
        else{
            v[pos] = arr[i];
        }
    }
    int ans = 0;
    for(int i = n; i >= 1; i--){
        ans = max(ans, LIS[i] + ask(1, 1, CAP, max(arr[i] - x + 1, 1), arr[i] + x - 1));
        update(1, 1, CAP, arr[i], ask(1, 1, CAP, arr[i] + 1, CAP) + 1);
    }
    cout << ans << '\n';
}

int main()
{
    int t = 1;
    while(t){
        t--;
        solve();
    }
}

Compilation message (stderr)

glo.cpp: In function 'void solve()':
glo.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         if(pos == v.size()){
      |            ~~~~^~~~~~~~~~~

• 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