Submission #561479

#	Time	Username	Problem	Language	Result	Execution time	Memory
561479		SirCovidThe19th	Financial Report (JOI21_financial)	C++17	100 / 100	521 ms	24652 KiB

Main

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

const int mx = 3e5 + 5;

int n, d, val[mx], ord[mx], par[mx], L[mx], seg[mx * 2]; set<int> S({-mx, mx * 2});

int get(int i){ 
    return i == par[i] ? i : par[i] = get(par[i]); 
}
void merge(int a, int b){
    a = get(a); b = get(b); 
    par[a] = b; L[b] = min(L[b], L[a]);
}
void upd(int i, int val){
    seg[i += mx] = val;
    for (i /= 2; i > 0; i /= 2) seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
}
int qry(int l, int r){ 
    int ret = 0;
    for (l += mx, r += mx; l <= r; r /= 2, l /= 2){
        if (l % 2 == 1) ret = max(ret, seg[l++]);
        if (r % 2 == 0) ret = max(seg[r--], ret);
    }
    return ret;
}

int main(){
    cin >> n >> d;
    for (int i = 1; i <= n; i++){
        cin >> val[i];
        par[i] = L[i] = ord[i] = i;
    }
    sort(ord + 1, ord + n + 1, [&](int a, int b){ 
        return val[a] != val[b] ? (val[a] < val[b]) : (a > b);
    });
    for (int i = 1; i <= n; i++){
        auto it = S.lower_bound(ord[i]);
        if (*it - ord[i] <= d) merge(ord[i], *it);
        if (ord[i] - *prev(it) <= d) merge(ord[i], *prev(it));
        S.insert(ord[i]);
        upd(ord[i], qry(L[get(ord[i])], ord[i]) + 1);
    }
    cout<<qry(1, mx)<<"\n";
}

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