Submission #216800

#	Time	Username	Problem	Language	Result	Execution time	Memory
216800		DystoriaX	Global Warming (CEOI18_glo)	C++14	100 / 100	183 ms	5496 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] - 1) - cmp.begin();
        auto id2 = upper_bound(cmp.begin(), cmp.end(), a[i] + x - 1) - cmp.begin();
        auto id = upper_bound(cmp.begin(), cmp.end(), a[i]) - cmp.begin();

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

        dp[0].update(id, dp[0].query(id1) + 1);
        dp[1].update(id, 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: 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