Submission #1122893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122893		SulA	Financial Report (JOI21_financial)	C++20	12 / 100	66 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;
    assert(d == 1);
    int a[n]; for (int i = 0; i < n; cin >> a[i++]);
    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;
}

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