Submission #441666

#	Time	Username	Problem	Language	Result	Execution time	Memory
441666		JovanB	Financial Report (JOI21_financial)	C++17	100 / 100	674 ms	28648 KiB

Main

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

using ll = long long;
using ld = long double;

const int MAXN = 300000;

struct DSU{
    int n;
    int par[MAXN+5];
    int sz[MAXN+5];
    int L[MAXN+5];
    int R[MAXN+5];
    DSU(int g){
        n = g;
        for(int i=1; i<=n; i++){
            par[i] = L[i] = R[i] = i;
            sz[i] = 1;
        }
    }
    int root(int x){ return par[x] == x ? x : par[x] = root(par[x]); }
    void povezi(int a, int b){
        int a1 = root(a);
        int b1 = root(b);
        if(a1 == b1) return;
        if(sz[a1] < sz[b1]) swap(a1, b1);
        sz[a1] += sz[b1];
        par[b1] = a1;
        L[a1] = min(L[a1], L[b1]);
        R[a1] = max(R[a1], R[b1]);
    }
};

pair <int, int> a[MAXN+5];
int seg[4*MAXN];

void upd(int node, int l, int r, int x, int val){
    if(l == r){
        seg[node] = max(seg[node], val);
        return;
    }
    int mid = (l+r)/2;
    if(x <= mid) upd(node*2, l, mid, x, val);
    else upd(node*2+1, mid+1, r, x, val);
    seg[node] = max(seg[node*2], seg[node*2+1]);
}

int query(int node, int l, int r, int tl, int tr){
    if(tl > r || l > tr) return 0;
    if(tl <= l && r <= tr) return seg[node];
    int mid = (l+r)/2;
    return max(query(node*2, l, mid, tl, tr), query(node*2+1, mid+1, r, tl, tr));
}

set <int> used;

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, d;
    cin >> n >> d;
    for(int i=1; i<=n; i++){
        cin >> a[i].first;
        a[i].second = -i;
    }
    sort(a+1, a+1+n);
    DSU dsu(n);
    int res = 0;
    for(int i=1; i<=n; i++){
        int ind = -a[i].second;
        auto ds = used.lower_bound(ind);
        if(ds != used.end() && *ds <= ind + d) dsu.povezi(ind, *ds);
        if(ds != used.begin()){
            ds--;
            if(*ds >= ind - d) dsu.povezi(ind, *ds);
        }
        int g = 1 + query(1, 1, n, dsu.L[dsu.root(ind)], ind);
        res = max(res, g);
        upd(1, 1, n, ind, g);
        used.insert(ind);
    }
    cout << res << "\n";
    return 0;
}

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