oj.uz

Submission #248624

# Submission time Handle Problem Language Result Execution time Memory
248624 2020-07-12T22:27:58 Z Sorting Global Warming (CEOI18_glo) C++14
48 / 100
 148 ms 5752 KB 
#include <bits/stdc++.h>

using namespace std;

const int k_N = 2e5 + 3;
const int k_Inf = 1e9 + 3;

struct Fenwick{
    int a[2 * k_N];

    void update(int i, int d){
        for(++i; i < k_N; i += i & -i)
            a[i] = max(d, a[i]);
    }

    int query(int i){
        int ans = 0;
        for(++i; i >= 1; i -= i & -i)
            ans = max(a[i], ans);
        return ans;
    }
};

int n, x;
int t[k_N], st[2 * k_N];

Fenwick f[2];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> x;
    for(int i = 0; i < n; ++i)
        cin >> t[i];

    for(int i = 0; i < n; ++i){
        st[2 * i] = t[i];
        st[2 * i + 1] = t[i] + x;
    }
    sort(st, st + 2 * n);

    for(int i = 0; i < n; ++i){
        int p1 = lower_bound(st, st + 2 * n, t[i]) - st;
        int p2 = lower_bound(st, st + 2 * n, t[i] + x) - st;

        int a = f[0].query(p1 - 1);
        int b = f[0].query(p2 - 1);
        int c = f[1].query(p2 - 1);

        f[0].update(p1, a + 1);
        f[1].update(p2, max(b, c) + 1);
    }

    cout << f[1].query(2 * n) << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 512 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2296 KB Output is correct
2 Correct 31 ms 2296 KB Output is correct
3 Correct 34 ms 2176 KB Output is correct
4 Correct 17 ms 1792 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 18 ms 2048 KB Output is correct
7 Correct 28 ms 2296 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 3192 KB Output is correct
2 Correct 74 ms 3192 KB Output is correct
3 Incorrect 148 ms 4984 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 512 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Incorrect 136 ms 5752 KB Output isn't correct
28 Halted 0 ms 0 KB -