Submission #1243969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243969		fskarica	Financial Report (JOI21_financial)	C++20	0 / 100	169 ms	18036 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second
#define pii pair<int, int>

const int INF = 1e9;
const int MAX = 3e5 + 10;
int n, d;
int x, y;
int arr[MAX];
int tree[4 * MAX];
pii treeTime[4 * MAX];
int lazyTime[4 * MAX];
int sol;

void input() {
    cin >> n >> d;

    vector <pii> v;
    for (int i = 1; i <= n; i++) {
        cin >> x;

        v.push_back({x, -i});
    }
    sort(v.begin(), v.end());

    int id = 0;
    for (auto e : v) arr[-e.se] = ++id;

//    cout << "arr: "; for (int i = 1; i <= n; i++) cout << arr[i] << " "; cout << "\n";
}

void update(int left, int right, int a, int idx, int val) {
    if (left > a || right < a) return;
    if (left == right) {
        tree[idx] = val;
        return;
    }

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

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

int query(int left, int right, int a, int b, int idx) {
    if (left > b || right < a) return 0;
    if (a <= left && right <= b) return tree[idx];

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

    return max(ret1, ret2);
}

pii spoji(pii a, pii b) {
    if (a.fi == 0) return b;
    if (b.fi == 0) return a;

    if (a.fi < b.fi) return a;
    if (b.fi < a.fi) return b;

    return {a.fi, min(a.se, b.se)};
}

void pushTime(int idx, int left, int right) {
    if (lazyTime[idx] == 0) return;

    int mid = (left + right) / 2;

    treeTime[idx * 2]     = {lazyTime[idx], left};
    treeTime[idx * 2 + 1] = {lazyTime[idx], mid + 1};
    lazyTime[idx * 2]     = lazyTime[idx];
    lazyTime[idx * 2 + 1] = lazyTime[idx];

    lazyTime[idx] = 0;
}

void updateTime(int left, int right, int a, int b, int idx, int val) {
    pushTime(idx, left, right);

    if (left > b || right < a) return;
    if (a <= left && right <= b) {
        treeTime[idx] = {val, left};
        lazyTime[idx] = val;
        return;
    }

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

    treeTime[idx] = spoji(treeTime[idx * 2], treeTime[idx * 2 + 1]);
}

pii queryTime(int left, int right, int a, int b, int idx) {
    pushTime(idx, left, right);

    if (left > b || right < a) return {INF, INF};
    if (a <= left && right <= b) return treeTime[idx];

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

    return spoji(ret1, ret2);
}

void removeTime(int t) {
//    cout << "removaj " << t << ": " << treeTime[1].fi << " " << treeTime[1].se << "\n";
    while (true) {
        pii bla = treeTime[1];
        if (bla.fi > t || bla.fi == 0) break;

//        cout << "removeTime: " << t << " | " << bla.fi << " " << bla.se << "\n";

        update(1, n, bla.se, 1, 0);
        updateTime(1, n, bla.se, bla.se, 1, 0);
    }
}

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

    input();

    for (int i = 1; i <= n; i++) {
//        if (i - d - 1 > 0) removeTime(i - d - 1);

        int x = arr[i];
        int maxx = query(1, n, 1, x, 1);

        update(1, n, x, 1, maxx + 1);
        updateTime(1, n, x, n, 1, i);

        sol = max(sol, maxx + 1);

//        cout << i << " - ";
//        for (int j = 1; j <= n; j++) cout << query(1, n, j, j, 1) << " " << queryTime(1, n, j, j, 1).fi << " " << queryTime(1, n, j, j, 1).se << " | ";
//        cout << "\n";
    }

    cout << sol << "\n";

    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35