제출 #950644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
950644		glebustim	Financial Report (JOI21_financial)	C++17	0 / 100	4090 ms	10980 KiB

Main

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
using oset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

const int R = (1 << 19);
vi t(R * 2, 0);

void update(int i, int x) {
    int v = R + i;
    t[v] = x;
    v >>= 1;
    while (v > 0) {
        t[v] = max(t[v << 1], t[(v << 1) ^ 1]);
        v >>= 1;
    }
}

int get_max(int l, int r) {
    l += R;
    r += R;
    int res = 0;
    while (l < r) {
        if (l & 1) {
            res = max(res, t[l]);
            ++l;
        }
        if (!(r & 1)) {
            res = max(res, t[r]);
            --r;
        }
        l >>= 1;
        r >>= 1;
    }
    if (l == r)
        res = max(res, t[l]);
    return res;
}

vi t1(R * 2, R);

void update1(int ql, int qr, int x, int v = 1, int l = 0, int r = R) {
    if (ql >= r || l >= qr)
        return;
    if (ql <= l && r <= qr) {
        t1[v] = min(t1[v], x);
        return;
    }
    int m = (l + r) / 2;
    update1(ql, qr, x, (v << 1), l, m);
    update1(ql, qr, x, ((v << 1) ^ 1), m, r);
}

int get1(int i) {
    int v = R + i, res = R;
    while (v > 0) {
        res = min(res, t1[v]);
        v >>= 1;
    }
    return res;
}

void compress(vi &a) {
    vi b = a;
    sort(all(b));
    for (int &x: a)
        x = lower_bound(all(b), x) - b.begin();
}

int main() {
    fast;
    int n, d;
    cin >> n >> d;
    vi a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    compress(a);
    vi r(n, n);
    for (int i = 0; i < n; ++i) {
        int c = 0;
        for (int j = i + 1; j < n; ++j) {
            if (a[j] > a[i]) {
                ++c;
                if (c == d) {
                    r[i] = j;
                    break;
                }
            }
            else
                c = 0;
        }
    }
//    multiset<int> s;
//    for (int i = n - d; i < n; ++i) {
//        r[i] = n;
//        s.insert(a[i]);
//    }
//    for (int i = n - d - 1; i >= 0; --i) {
//        update1(0, *s.begin(), i);
//        r[i] = min(get1(a[i]) + d, n);
//        s.erase(s.find(a[i + d]));
//        s.insert(a[i]);
//    }
    vi b(n, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (r[j] >= i && a[j] < a[i])
                b[i] = max(b[i], b[j]);
        }
        ++b[i];
    }
//    vector<multiset<int>> c(n);
//    for (int i = 0; i < n; ++i)
//        c[i].insert(0);
//    multiset<tuple<int, int, int>> ss;
//    for (int i = 0; i < n; ++i) {
//        b[i] = get_max(0, a[i] - 1) + 1;
//        ss.emplace(r[i], a[i], b[i]);
//        c[a[i]].insert(b[i]);
//        update(a[i], *(--c[a[i]].end()));
//        while (!ss.empty() && get<0>(*ss.begin()) == i) {
//            c[get<1>(*ss.begin())].erase(c[get<1>(*ss.begin())].find(get<2>(*ss.begin())));
//            update(get<1>(*ss.begin()), *(--c[get<1>(*ss.begin())].end()));
//            ss.erase(ss.begin());
//        }
//    }
    int ans = 0;
    for (int i = max(n - d - 1, 0); i < n; ++i)
        ans = max(ans, b[i]);
    cout << ans << '\n';
}

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