oj.uz

Submission #463754

# Submission time Handle Problem Language Result Execution time Memory
463754 2021-08-11T17:23:25 Z idk321 Global Warming (CEOI18_glo) C++17
52 / 100
 811 ms 37784 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MIN = -2000000001;
const int MAX = 2000000001;

int n, x;
const int N = 200005;
int tree[4 * N][2];

int getMax(int from, int to, int a, int b, int node, int treeNum) {
    if (from > to) return 0;
    if (from <= a && b <= to) return tree[node][treeNum];

    int mid = (a + b) / 2;
    int res = -1;
    if (from <= mid) res = max(res, getMax(from, to, a, mid, node * 2, treeNum));
    if (to > mid) res = max(res, getMax(from, to, mid +1, b, node * 2 + 1, treeNum));

    return res;
}

void insertMax(int i, int num, int a, int b, int node, int treeNum) {
    if (a == b) {
        tree[node][treeNum] = max(tree[node][treeNum], num);
        return;
    }

    int mid = (a + b) / 2;
    if (i <= mid) insertMax(i, num, a, mid, node * 2, treeNum);
    else insertMax(i, num, mid + 1, b, node * 2 + 1, treeNum);
    tree[node][treeNum] = max(tree[node * 2][treeNum], tree[node * 2 + 1][treeNum]);
}

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

    cin >> n >> x;
    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    if (n == 1) {
        cout << 1 << "\n";
        return 0;
    }
    vector<int> left(n);

    set<int> all;
    map<int, int> mapTo;
    for (int i = 0; i < n; i++) all.insert(v[i]);
    int cur = 0;
    for (int i : all) {
        mapTo[i] = cur;
        cur++;
    }

    vector<int> getsTo(n);
    vector<int> org(v.begin(), v.end());
    set<array<int, 2>> orgAndNew;
    for (int i = 0; i < n; i++) {
        v[i] = mapTo[v[i]];
        orgAndNew.insert({org[i], v[i]});
    }

    for (int i = 0; i < n; i++) {
        auto it = orgAndNew.upper_bound({org[i] + x, -1});
        it--;
        getsTo[v[i]] = (*it)[1];
    }

    for (int i = 0; i < n; i++) {
        insertMax(v[i], 1 + getMax(0, getsTo[v[i]], 0, N - 1, 1, 0), 0, N - 1, 1, 1);
        insertMax(v[i], 1 + getMax(0, v[i] - 1, 0, N - 1, 1, 0), 0, N - 1, 1, 0);
        insertMax(v[i], 1 + getMax(0, v[i] - 1, 0, N - 1, 1, 1), 0, N - 1, 1, 1);
    }

    cout << getMax(0, N - 1, 0, N - 1, 1, 1) << "\n";
}

/*
8 10
7 3 5 12 2 7 3 4
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Incorrect 1 ms 332 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Incorrect 1 ms 332 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 37676 KB Output is correct
2 Correct 778 ms 37784 KB Output is correct
3 Correct 772 ms 37660 KB Output is correct
4 Correct 811 ms 37704 KB Output is correct
5 Correct 329 ms 20684 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 9664 KB Output is correct
2 Correct 140 ms 9796 KB Output is correct
3 Correct 143 ms 9696 KB Output is correct
4 Correct 77 ms 5472 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 84 ms 5412 KB Output is correct
7 Correct 117 ms 9664 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 19108 KB Output is correct
2 Correct 293 ms 19084 KB Output is correct
3 Correct 712 ms 37712 KB Output is correct
4 Correct 335 ms 20764 KB Output is correct
5 Correct 213 ms 18520 KB Output is correct
6 Correct 420 ms 35200 KB Output is correct
7 Correct 403 ms 35860 KB Output is correct
8 Correct 246 ms 19096 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Incorrect 1 ms 332 KB Output isn't correct
14 Halted 0 ms 0 KB -