Submission #575679

#	Time	Username	Problem	Language	Result	Execution time	Memory
575679		vaaven	Financial Report (JOI21_financial)	C++14	100 / 100	514 ms	29796 KiB

Main

#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
//#pragma GCC target("popcnt")
//#pragma comment(linker, "/STACK:36777216")
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <tuple>
#include <math.h>
#include <set>
#include <stack>
#include <bitset>
#include <map>
#include <queue>
#include <random>
#include <array>
#include <unordered_set>
#include <cmath>
#include <cassert>
#include <unordered_map>

#define DEBUG
#define pqueue priority_queue
#define pb(x) push_back(x)
#define endl '\n'
#define all(x) x.begin(), x.end()
//#define int long long

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ull> vull;
typedef vector<ll> vll;
// typedef tuple<ll, ll, ll> tiii;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<vector<int> > vvi;
typedef vector<char> vc;

const ll inf = 1e9 + 228;
const ll infll = 1e18 + 228;
const ll mod = 1e9 + 7;
const ll mod3 = 1e9 + 7;
//static const int maxn = 1e6 + 228;
const ld eps = 1e-6;
const ll mod2 = 998244353;
const ld PI = atan2l(0, -1);

void fast_io() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    freopen("input.txt", "r", stdin);
//    freopen("lumber.out", "w", stdout);
}

const int maxn = 3e5 + 228;
int link[maxn];
int sz[maxn];
int lef[maxn];

int find(int v) {
    if (link[v] == v)
        return v;
    return link[v] = find(link[v]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)
        return;
    if (sz[a] > sz[b])
        swap(a, b);
    sz[b] += sz[a];
    link[a] = b;
    lef[b] = min(lef[b], lef[a]);
}

bool cmp(pii a, pii b) {
    if (a.first == b.first) {
        return a.second > b.second;
    } else {
        return a.first < b.first;
    }
}

int t[maxn * 4];

int get(int v, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return t[v];
    } else if (l > qr || ql > r) {
        return 0;
    } else {
        int mid = (l + r) / 2;
        return max(get(v * 2, l, mid, ql, qr), get(v * 2 + 1, mid + 1, r, ql, qr));
    }
}

void upd(int v, int l, int r, int k, int k_new) {
    if (l == r) {
        t[v] = k_new;
    } else {
        int mid = (l + r) / 2;
        if (k <= mid) {
            upd(v * 2, l, mid, k, k_new);
        } else {
            upd(v * 2 + 1, mid + 1, r, k, k_new);
        }
        t[v] = max(t[v * 2], t[v * 2 + 1]);
    }
}

void solve() {
    for (int i = 0; i < maxn; i++) {
        link[i] = i;
        sz[i] = 1;
        lef[i] = i;
    }
    int n, d;
    cin >> n >> d;
    vector<int> a(n);
    for (int &i: a)
        cin >> i;
    vector<pii> kek;
    for (int i = 0; i < n; i++) {
        kek.pb(make_pair(a[i], i));
    }
    sort(all(kek), cmp);
    set<int> lol;
    vector<int> dp(n, 0);
    for (pii i: kek) {
        auto it = lol.lower_bound(i.second);
        if (it != lol.end()) {
            if (abs(i.second - *it) <= d)
                unite(i.second, *it);
        }
        if (it != lol.begin()) {
            it--;
            if (abs(i.second - *it) <= d)
                unite(i.second, *it);
        }
        lol.insert(i.second);
        int root = find(i.second);
        int l = lef[root];
        dp[i.second] = get(1, 0, maxn, max(l - d, 0), i.second - 1) + 1;
        upd(1, 0, maxn, i.second, dp[i.second]);
    }
    cout << *max_element(all(dp)) << endl;
}

/*
7 1
100 600 600 200 300 500 500
========
6 6
100 500 200 400 600 300
========
11 2
1 4 4 2 2 4 9 5 7 0 3
 */


signed main() {
    srand(time(NULL));
    fast_io();
    int q = 1;
//    cin >> q;
    while (q--) {
        solve();
    }
    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