Submission #1122896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122896		SulA	Financial Report (JOI21_financial)	C++20	17 / 100	84 ms	8124 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC target("popcnt")
using namespace __gnu_pbds;
using namespace std;
using ordered_set = tree<int, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update>;
#define popcount __builtin_popcountll
#define all(a) (a).begin(), (a).end()

struct segtree {
    vector<int> tree;
    int offset = 1;
    segtree(int n) {
        while (offset < n) offset <<= 1;
        tree.resize(offset << 1, 0);
    }
    void update(int i) {
        tree[i += offset]++;
        while (i >>= 1) tree[i] = tree[2*i] + tree[2*i+1];
    }
    int query(int v, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[v];
        if (qr < l || r < ql) return 0;
        int mid = (l+r)/2;
        return query(2*v, l, mid, ql, qr) +
            query(2*v+1, mid+1, r, ql, qr);
    }
    int query(int l, int r) {
        return query(1, 0, offset - 1, l, r);
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n,d; cin >> n >> d;
    int a[n];
    for (int i = 0; i < n; cin >> a[i++]);
    if (d == 1) {
        int l[n];
        vector<int> stack;
        for (int i = 0; i < n; i++) {
            while (!stack.empty() && a[stack.back()] < a[i]) stack.pop_back();
            l[i] = stack.empty() ? 0 : stack.back() + 1;
            stack.push_back(i);
        }
        segtree s(n);
        int ans = 0;
        for (int i = n - 1; i >= 0; i--) {
            s.update(l[i]);
            ans = max(ans, s.query(0, i));
        }
        cout << ans;
    } else if (d == n) {
        vector<int> lis;
        for (int i = 0; i < n; i++) {
            if (lis.empty() || a[i] > lis.back()) lis.push_back(a[i]);
            else *lower_bound(lis.begin(), lis.end(), a[i]) = a[i];
        }
        cout << lis.size();
    }
}

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