제출 #1243912

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243912		fskarica	Financial Report (JOI21_financial)	C++20	5 / 100	147 ms	5848 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 MAX = 3e5 + 10;
int n, d;
int x, y;
int arr[MAX];
int tree[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);
}

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

    input();

    for (int i = 1; i <= n; i++) {
        int x = arr[i];
        int maxx = query(1, n, 1, x, 1);

        update(1, n, x, 1, maxx + 1);
//        if (i - d >= 1) update(1, n, arr[i - d], 1, 0);

        sol = max(sol, maxx + 1);
    }

    cout << sol << "\n";

    return 0;
}

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