Submission #216795

#	Time	Username	Problem	Language	Result	Execution time	Memory
216795		DystoriaX	Global Warming (CEOI18_glo)	C++14	0 / 100	132 ms	5368 KiB

glo

#include <bits/stdc++.h>

using namespace std;

const int MAX = 2e5 + 10;

class BIT{
private:
    vector<int> bit;

public:
    void update(int x, int val){
        for(; x < MAX; x += x & (-x)) bit[x] = max(bit[x], val);
    }

    int query(int x){
        int ret = 0;
        for(; x; x -= x & (-x)) ret = max(ret, bit[x]);

        return ret;
    }

    BIT(){
        bit.assign(MAX, 0);
    }
};

int n, x;
int a[200010];
vector<int> cmp;
int ans;
BIT dp[2];

int main(){
    scanf("%d%d", &n, &x);

    cmp.resize(n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]), cmp[i - 1] = a[i];

    sort(cmp.begin(), cmp.end());
    cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());

    for(int i = 1; i <= n; i++){
        auto id1 = upper_bound(cmp.begin(), cmp.end(), a[i]) - cmp.begin(); //a[i] - 1
        auto id2 = upper_bound(cmp.begin(), cmp.end(), a[i] + x) - cmp.begin(); //a[i] + x - 1

        int val1 = dp[1].query(id1) + 1;
        int val2 = dp[0].query(id2) + 1;

        dp[0].update(a[i], dp[0].query(id1) + 1);
        dp[1].update(a[i], max(val1, val2));
    }

    printf("%d\n", dp[1].query(MAX - 1));
    
    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &x);
     ~~~~~^~~~~~~~~~~~~~~~
glo.cpp:38:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; i++) scanf("%d", &a[i]), cmp[i - 1] = a[i];
                                 ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25