Submission #1280866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280866		am_aadvik	Financial Report (JOI21_financial)	C++20	0 / 100	4089 ms	1114112 KiB

Main

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;

class segtree1 {
private:
    vector<int> st, lazy, a;
    const int dv = 2e9;
    const int ldv = 0;
    int join(int l, int r) {
        return min(l, r);
    }
    int ljoin(int l, int r) {
        return l + r;
    }
    void upd(int s, int e, int node, int val) {
        if (val == ldv) return;
        st[node] += ((e - s + 1) * val);
    }

    int build(int s, int e, int node) {
        if (s == e)
            return st[node] = a[s];
        int mid = (s + e) / 2;
        return st[node] = join(build(s, mid, node * 2), build(mid + 1, e, node * 2 + 1));
    }

    void update(int s, int e, int node, int l, int r, int val) {
        if ((l > e) || (r < s)) return;
        if ((l <= s) && (r >= e)) {
            upd(s, e, node, val);
            lazy[node] = ljoin(lazy[node], val);
            return;
        }

        int mid = (s + e) / 2;
        upd(s, mid, node * 2, lazy[node]);
        upd(mid + 1, e, node * 2 + 1, lazy[node]);
        lazy[node * 2] = ljoin(lazy[node * 2], lazy[node]);
        lazy[node * 2 + 1] = ljoin(lazy[node * 2 + 1], lazy[node]);
        lazy[node] = ldv;

        update(s, mid, node * 2, l, r, val);
        update(mid + 1, e, node * 2 + 1, l, r, val);
        st[node] = join(st[node * 2], st[node * 2 + 1]);
    }

    int query(int s, int e, int node, int l, int r) {
        if ((l > e) || (r < s)) return dv;
        if ((l <= s) && (r >= e)) return st[node];

        int mid = (s + e) / 2;
        upd(s, mid, node * 2, lazy[node]);
        upd(mid + 1, e, node * 2 + 1, lazy[node]);
        lazy[node * 2] = ljoin(lazy[node * 2], lazy[node]);
        lazy[node * 2 + 1] = ljoin(lazy[node * 2 + 1], lazy[node]);
        lazy[node] = ldv;

        return join(query(s, mid, node * 2, l, r),
            query(mid + 1, e, node * 2 + 1, l, r));
    }

public:
    segtree1(int n, vector<int> arr) {
        a = arr;
        st.resize(4 * n, dv);
        lazy.resize(4 * n, ldv);
        build(0, n - 1, 1);
    }

    int query(int l, int r) {
        return query(0, a.size() - 1, 1, l, r);
    }

    void update(int l, int r, int val) {
        update(0, a.size() - 1, 1, l, r, val);
    }
};
class segtree2 {
private:
    vector<int> st, lazy, a;
    const int dv = 0;
    const int ldv = 0;
    int join(int l, int r) {
        return max(l, r);
    }
    int ljoin(int l, int r) {
        return r;
    }
    void upd(int s, int e, int node, int val) {
        if (val == ldv) return;
        st[node] = ((e - s + 1) * val);
    }

    int build(int s, int e, int node) {
        if (s == e)
            return st[node] = a[s];
        int mid = (s + e) / 2;
        return st[node] = join(build(s, mid, node * 2), build(mid + 1, e, node * 2 + 1));
    }

    void update(int s, int e, int node, int l, int r, int val) {
        if ((l > e) || (r < s)) return;
        if ((l <= s) && (r >= e)) {
            upd(s, e, node, val);
            lazy[node] = ljoin(lazy[node], val);
            return;
        }

        int mid = (s + e) / 2;
        upd(s, mid, node * 2, lazy[node]);
        upd(mid + 1, e, node * 2 + 1, lazy[node]);
        lazy[node * 2] = ljoin(lazy[node * 2], lazy[node]);
        lazy[node * 2 + 1] = ljoin(lazy[node * 2 + 1], lazy[node]);
        lazy[node] = ldv;

        update(s, mid, node * 2, l, r, val);
        update(mid + 1, e, node * 2 + 1, l, r, val);
        st[node] = join(st[node * 2], st[node * 2 + 1]);
    }

    int query(int s, int e, int node, int l, int r) {
        if ((l > e) || (r < s)) return dv;
        if ((l <= s) && (r >= e)) return st[node];

        int mid = (s + e) / 2;
        upd(s, mid, node * 2, lazy[node]);
        upd(mid + 1, e, node * 2 + 1, lazy[node]);
        lazy[node * 2] = ljoin(lazy[node * 2], lazy[node]);
        lazy[node * 2 + 1] = ljoin(lazy[node * 2 + 1], lazy[node]);
        lazy[node] = ldv;

        return join(query(s, mid, node * 2, l, r),
            query(mid + 1, e, node * 2 + 1, l, r));
    }

public:
    segtree2(int n, vector<int> arr) {
        a = arr;
        st.resize(4 * n, dv);
        lazy.resize(4 * n, ldv);
        build(0, n - 1, 1);
    }

    int query(int l, int r) {
        return query(0, a.size() - 1, 1, l, r);
    }

    void update(int l, int r, int val) {
        update(0, a.size() - 1, 1, l, r, val);
    }
};
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int t; cin >> t;
    while (t--) {
        int n, d, ans = 0; cin >> n >> d;
        vector<int> a(n);
        for (auto& x : a) cin >> x;

        vector<pair<int, int>> arr;
        vector<int> ld(n, n - 1);
        segtree1 st1(n, a);
        for (int i = n - 1; i >= (d - 1); --i)
            arr.push_back({ st1.query(i - d + 1, i), i });
        sort(arr.begin(), arr.end());
        vector<pair<int, int>> sa(n);
        set<int> s;
        for (int i = 0; i < n; ++i) sa[i] = { a[i], i };
        sort(sa.begin(), sa.end());

        int j = arr.size() - 1;
        for (int i = n - 1; i >= 0; --i) {
            while ((j >= 0) && (arr[j].first > sa[i].first))
                s.insert(arr[j].second), j--;
            auto it = s.lower_bound(sa[i].second + 1);
            if (it != s.end()) ld[sa[i].second] = *it;
        }

        vector<int> dp(n, -1e9);
        segtree2 st2(n, dp);
        vector<pair<int, vector<int>>> v;
        for (int i = 0; i < n; ++i)
            if ((i == 0) || (sa[i - 1].first < sa[i].first))
                v.push_back({ sa[i].first, {sa[i].second} });
        int m = v.size();
        for (int i = m - 1; i >= 0; --i) {
            for (auto x : v[i].second)
                dp[x] = max(1, st2.query(x + 1, ld[x]) + 1);
            for (auto x : v[i].second)
                st2.update(x, x, dp[x]);
        }
        for (auto x : dp) ans = max(ans, x);
        cout << ans << endl;
    }
}

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