Submission #499724

#	Time	Username	Problem	Language	Result	Execution time	Memory
499724		Sho10	Financial Report (JOI21_financial)	C++17	5 / 100	326 ms	18592 KiB

Main

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct seg_tree {
 
    int B;
    vector<int> val;
 
    void init(int x) {
        B = 1;
        while(B < x) B *= 2;
        val.assign(B * 2, 0);
    }
 
    int merge(int a, int b) {
        return max(a, b);
    }
 
    void upd(int node, int l, int r, int pos, int x) {
        if (r - l == 1) {
            val[node] = x;
            return;
        }
        int mid = (l + r) / 2;
        if (mid > pos) upd(node * 2 + 1, l, mid, pos, x);
        if (mid <= pos) upd(node * 2 + 2, mid, r, pos, x);
        val[node] = merge(val[node * 2 + 1], val[node * 2 + 2]);
    }
    void upd(int pos, int x) {
        upd(0, 0, B, pos, x);
    }
 
    int ask(int node, int l, int r, int st, int dr) {
        if (dr <= l || st >= r) return 0;
        if (l >= st && r <= dr) return val[node];
        int mid = (l + r) / 2;
        return max(ask(node * 2 + 1, l, mid, st, dr),
                   ask(node * 2 + 2, mid, r, st, dr));
    }
    int ask(int st, int dr) {
        return ask(0, 0, B, st, dr);
    }
} ST;
int N, d;
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> d;
    ST.init(N + 66);
    vector<int> a(N);
    for(int &x : a) {
        cin >> x;
    }
    vector<int> b = a;
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    for(int i = 0; i < N; ++i) {
        int mapping = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
        a[i] = mapping + 1;
    }
    vector<int> last(N + 6);
    int answer = 0;
    for(int i = 0; i < N; ++i) {
        if(i - d - 1 >= 0 && last[a[i - d - 1]] == i - d - 1) {
            ST.upd(a[i - d - 1], 0);
        }
        int tmp = ST.ask(1, a[i]) + 1;
        int maybe = ST.ask(a[i], N + 1);
        answer = max(answer, max(maybe, tmp));
        ST.upd(a[i], tmp);
        last[a[i]] = i;
    }
    cout << answer << '\n';
    return 0;
}

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