oj.uz

Submission #216795

# Submission time Handle Problem Language Result Execution time Memory
216795 2020-03-28T04:39:20 Z DystoriaX Global Warming (CEOI18_glo) C++14
0 / 100
 132 ms 5368 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 5368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 2816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 3712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1920 KB Output isn't correct
2 Halted 0 ms 0 KB -