Submission #1121217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121217		thangdz2k7	Financial Report (JOI21_financial)	C++17	100 / 100	411 ms	25676 KiB

Main

// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using ii = pair <int, int>;
using vi = vector <int>;

const int N = 3e5 + 5;
const int mod = 1e9 + 7;

int n, d, ans = 0;
pair <int, int> a[N];
set <int> s;

struct DSU{
    vi par;

    DSU(int n){
        par.resize(n);
        for (int i = 0; i < n; ++ i) par[i] = i;
    }

    int find(int u){
        if (u == par[u]) return u;
        return par[u] = find(par[u]);
    }

    bool check(int u, int v){
        return find(u) == find(v);
    }

    void joint(int u, int v){
        u = find(u); v = find(v);
        par[u] = v;
    }
};

int Max[N << 2];

void update(int u, int v, int val, int s = 1, int l = 1, int r = n){
    if (u <= l && r <= v) {
        Max[s] = max(Max[s], val);
        return;
    }

    int mid = l + r >> 1;
    if (mid >= u) update(u, v, val, s << 1, l, mid);
    if (mid < v) update(u, v, val, s << 1 | 1, mid + 1, r);
}

int get(int u, int s = 1, int l = 1, int r = n){
    if (l == r) return Max[s];

    int mid = l + r >> 1;
    if (mid >= u) return max(get(u, s << 1, l, mid), Max[s]);
    return max(get(u, s << 1 | 1, mid + 1, r), Max[s]);
}

void solve(){
    cin >> n >> d;
    for (int i = 1; i <= n; ++ i){
        cin >> a[i].fi;
        a[i].se = i, a[i].fi = -a[i].fi;
    }
    sort(a + 1, a + n + 1);

    s.insert(mod);
    s.insert(-mod);

    DSU T(n + 1);

    for (int ord = n; ord >= 1; -- ord){
        int p = a[ord].se;
        s.insert(p);
        int cur = get(p) + 1;
        ans = max(ans, cur);

        int nxt = *s.upper_bound(p);
        if (p + d >= nxt) T.joint(p, nxt);

        int r = T.find(p);
        r = min(n, r + d);
        update(p, r, cur);

        int lst = *(--s.lower_bound(p));
        if (p - d <= lst) T.joint(lst, p);
    }

    cout << ans;
}

int main(){
    if (fopen("pqh.inp", "r")){
        freopen("pqh.inp", "r", stdin);
        freopen("pqh.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1; // cin >> t;
    while (t --) solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void update(int, int, int, int, int, int)':
Main.cpp:53:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'int get(int, int, int, int)':
Main.cpp:61:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen("pqh.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen("pqh.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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