oj.uz

Submission #424216

# Submission time Handle Problem Language Result Execution time Memory
424216 2021-06-11T18:08:52 Z fskarica Global Warming (CEOI18_glo) C++14
10 / 100
 353 ms 15796 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second

const int MAX = 4e5 + 10;
int n, k;
int x, y;
int ucit[MAX];
int arr[MAX];
int treeFront[4 * MAX];
int treeBack[4 * MAX];
int dpFront[MAX];
int dpBack[MAX];
vector <int> v;
map <int, int> mp;
int id;

void updateFront(int left, int right, int a, int idx, int val) {
    if (left > a || a > right) return;
    if (left == right) {
        treeFront[idx] = max(treeFront[idx], val);
        return;
    }

    int mid = (left + right) / 2;
    updateFront(left, mid, a, idx * 2, val);
    updateFront(mid + 1, right, a, idx * 2 + 1, val);

    treeFront[idx] = max(treeFront[idx * 2], treeFront[idx * 2 + 1]);
}

void updateBack(int left, int right, int a, int idx, int val) {
    if (left > a || a > right) return;
    if (left == right) {
        treeBack[idx] = max(treeBack[idx], val);
        return;
    }

    int mid = (left + right) / 2;
    updateBack(left, mid, a, idx * 2, val);
    updateBack(mid + 1, right, a, idx * 2 + 1, val);

    treeBack[idx] = max(treeBack[idx * 2], treeBack[idx * 2 + 1]);
}

int queryFront(int left, int right, int a, int idx) {
    if (left > a) return 0;
    if (a >= right) {
        return treeFront[idx];
    }

    int mid = (left + right) / 2;
    int ret1 = queryFront(left, mid, a, idx * 2);
    int ret2 = queryFront(mid + 1, right, a, idx * 2 + 1);

    return max(ret1, ret2);
}

int queryBack(int left, int right, int a, int idx) {
    if (right < a) return 0;
    if (a <= left) {
        return treeBack[idx];
    }

    int mid = (left + right) / 2;
    int ret1 = queryBack(left, mid, a, idx * 2);
    int ret2 = queryBack(mid + 1, right, a, idx * 2 + 1);

    return max(ret1, ret2);
}

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

    cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        cin >> ucit[i];

        v.push_back(ucit[i]);
        v.push_back(ucit[i] + k);
    }
    sort(v.begin(), v.end());

    mp[v[0]] = 0;

    id = 1;
    for (int i = 1; i < v.size(); i++) {
        if (v[i] == v[i - 1]) continue;

        mp[v[i]] = id;
        id++;
    }

    for (int i = 1; i <= n; i++) {
        arr[i] = mp[ucit[i]];
    }

    for (int i = n; i >= 1; i--) {
        x = arr[i];

        dpBack[i] = queryBack(0, 2 * n - 1, x + 1, 1) + 1;
        updateBack(0, 2 * n - 1, x, 1, dpBack[i]);
    }

    cout << treeBack[1] << "\n";
    return 0;

    int sol = queryBack(0, 2 * n - 1, -1, 1);
    for (int i = 1; i < n; i++) {
        x = arr[i];

        dpFront[i] = queryFront(0, 2 * n - 1, x - 1, 1) + 1;
        updateFront(0, 2 * n - 1, x, 1, dpFront[i]);

        sol = max(sol, queryFront(0, 2 * n - 1, mp[ucit[i + 1] + k] - 1 , 1) + dpBack[i + 1]);
    }

    cout << sol << "\n";

    return 0;
}

Compilation message

glo.cpp: In function 'int main()':
glo.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = 1; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 13.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 15608 KB Output is correct
2 Correct 353 ms 15652 KB Output is correct
3 Correct 327 ms 15796 KB Output is correct
4 Correct 318 ms 15752 KB Output is correct
5 Correct 146 ms 9972 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 6988 KB Output is correct
2 Correct 77 ms 6948 KB Output is correct
3 Correct 93 ms 6968 KB Output is correct
4 Incorrect 45 ms 4164 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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

Subtask #7
0 / 25.0

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