oj.uz

Submission #424184

# Submission time Handle Problem Language Result Execution time Memory
424184 2021-06-11T17:46:26 Z fskarica Global Warming (CEOI18_glo) C++14
17 / 100
 725 ms 27904 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int MAX = 2e5 + 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() {
    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, n - 1, x + 1, 1) + 1;
        updateBack(0, n - 1, x, 1, dpBack[i]);
    }

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

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

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

    cout << sol << "\n";

    return 0;
}

Compilation message

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 20.0

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

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 14016 KB Output is correct
2 Correct 302 ms 14104 KB Output is correct
3 Correct 725 ms 27904 KB Output is correct
4 Correct 331 ms 16436 KB Output is correct
5 Correct 199 ms 14200 KB Output is correct
6 Correct 364 ms 26800 KB Output is correct
7 Correct 387 ms 26708 KB Output is correct
8 Correct 241 ms 14020 KB Output is correct

Subtask #7
0 / 25.0

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