Submission #424210

#	Time	Username	Problem	Language	Result	Execution time	Memory
424210		fskarica	Global Warming (CEOI18_glo)	C++14	10 / 100	419 ms	17668 KiB

glo

#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 (stderr)

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25