Submission #950648

#	Time	Username	Problem	Language	Result	Execution time	Memory
950648		glebustim	Financial Report (JOI21_financial)	C++17	100 / 100	684 ms	90232 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);
    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);
    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 = 0; i < n; ++i) {
        if (r[i] >= n - 1)
            ans = max(ans, b[i]);
    }
    cout << ans << '\n';
}

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