Submission #1229728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229728		SpyrosAliv	Financial Report (JOI21_financial)	C++20	5 / 100	1343 ms	54564 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 1e9;
int n, d;
vector<int> arr;

class segTree {
    private:
    vector<int> seg;
    int query(int node, int start, int end, int l, int r) {
        if (start > r || end < l) return 0;
        else if (start >= l && end <= r) return seg[node];
        else {
            int mid = (start + end) / 2;
            return max(query(node*2, start, mid, l, r), query(node*2+1, mid+1, end, l, r));
        }
    }
    void update(int node, int start, int end, int idx, int v) {
        if (start == end) {
            seg[node] = v;
        }
        else {
            int mid = (start + end) / 2;
            if (idx <= mid) update(node*2, start, mid, idx, v);
            else update(node*2+1, mid+1, end, idx, v);
            seg[node] = max(seg[node*2], seg[node*2+1]);
        }
    }
    public:
    segTree(int nn) {
        n = nn;
        seg.assign(n*4+10, 0);
    }
    int query(int l, int r) {
        l = max(0LL, l);
        if (l > r) return 0;
        return query(1, 0, n-1, l, r);
    }
    void update(int idx, int v) {
        update(1, 0, n-1, idx, v);
    }
};

class maxSeg {
    private:
    struct Node {
        int pref = 1, suff = 1, tot = 1, maxS = 1;
    };
    Node merge(Node a, Node b) {
        Node c;
        c.pref = max(a.pref, a.tot + b.pref);
        c.suff = max(b.suff, b.tot + a.suff);
        c.tot = a.tot + b.tot;
        c.maxS = a.suff + b.pref;
        return c;
    }
    vector<Node> seg;
    void build(int node, int l, int r) {
        if (l == r) {
            Node foo;
            seg[node] = foo;
        }
        else {
            int mid = (l + r) / 2;
            build(node*2, l, mid);
            build(node*2+1, mid+1, r);
            seg[node] = merge(seg[node*2], seg[node*2+1]);
        }
    }
    Node query(int node, int start, int end, int l, int r) {
        if (start > r || end < l) {
            Node foo;
            return foo;
        }
        else if (start >= l && end <= r) return seg[node];
        else {
            int mid = (start + end) / 2;
            return merge(query(node*2, start, mid, l, r), query(node*2+1, mid+1, end, l, r));
        }
    }
    void update(int node, int start, int end, int idx) {
        if (start == end) {
            seg[node] = {-INF, -INF, -INF, -INF};
        }
        else {
            int mid = (start + end) / 2;
            if (idx <= mid) update(node*2, start, mid, idx);
            else update(node*2+1, mid+1, end, idx);
            seg[node] = merge(seg[node*2], seg[node*2+1]);
        }
    }
    public:
    maxSeg(int nn) {
        n = nn;
        Node foo;
        seg.assign(n*4+10, foo);
        build(1, 0, n-1);
    }
    int query(int l, int r) {
        l = max(0LL, l);
        if (l > r) return 0;
        return query(1, 0, n-1, l, r).maxS;
    }
    void enable(int idx) {
        update(1, 0, n-1, idx);
    }
};

void compress() {
    vector<pair<int, int>> vals;
    for (int i = 0; i < n; i++) vals.push_back({arr[i], i});
    sort(vals.begin(), vals.end());
    int t = 0;
    for (int i = 0; i < n; i++) {
        if (i > 0 && vals[i].first != vals[i-1].first) t++;
        arr[vals[i].second] = t;
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> d;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        arr.push_back(x);
    }
    segTree dp(n);
    vector<pair<int, int>> vals;
    for (int i = 0; i < n; i++) {
        vals.push_back({arr[i], i});
    }
    sort(vals.begin(), vals.end(), [&](pair<int, int> a, pair<int, int> b) {
        if (a.first != b.first) return a.first < b.first;
        else return a.second > b.second;
    });
    int ans = 0;
    maxSeg maxRange(n);
    for (auto [foo, idx]: vals) {
        int lo = 0, hi = idx-1;
        int fin = idx-d;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            int maxSeg = maxRange.query(mid, idx-1);
            if (maxSeg >= d) {
                lo = mid+1;
            }
            else {
                hi = mid-1;
                fin = min(fin, mid);
            }
        }
        int dp2 = dp.query(fin, idx) + 1;
        ans = max(ans, dp2);
        dp.update(idx, dp2);
        maxRange.enable(idx);
    }
    cout << ans << "\n";
}

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