Submission #1225872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225872		bangan	Financial Report (JOI21_financial)	C++20	0 / 100	1 ms	1348 KiB

Main

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

#define ll long long
#define int long long

#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)

#define FOR1(a) for (int _ = 1; _ <= (a); _++)
#define FOR2(i, a) for (int i = 1; i <= (a); i++)
#define FOR3(i, a, b) for (int i = (a); i <= (b); i++)
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload3(__VA_ARGS__, FOR3, FOR2, FOR1)(__VA_ARGS__)

#define sep ' '
#define endl '\n'
#define print(a) cerr << #a << " = " << a << endl;

#define X first
#define Y second
#define MP make_pair
#define MT make_tuple
#define pii pair<int, int>

#define pb push_back
#define eb emplace_back
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) sort(ALL(a)); a.resize(unique(ALL(a)) - a.begin());

#define LC (v << 1)
#define RC (LC | 1)
#define mid ((l+r) / 2)

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 7000 + 4;
const int INF = 1ll << 60;

int n, d;
int a[N];

struct Info {
    int dp, mn, pos, lz;
    Info(): dp(0), mn(INF), pos(0), lz(-1) {};
    Info(int x, int y, int z, int t): dp(x), mn(y), pos(z), lz(t) {};
} seg[4*N];

Info merge(Info a, Info b) {
    assert(a.lz == -1);
    assert(b.lz == -1);
    Info ret;
    ret.dp = max(a.dp, b.dp);
    if (a.mn < b.mn) ret.mn = a.mn, ret.pos = a.pos;
    else             ret.mn = b.mn, ret.pos = b.pos;
    return ret;
}

void push(int v) {
    chmax(seg[v].mn, seg[v].lz);
    if (LC < 4*n) chmax(seg[LC].lz, seg[v].lz);
    if (RC < 4*n) chmax(seg[RC].lz, seg[v].lz);
    seg[v].lz = -1;
}

void pull(int v) {
    push(v);
    push(LC);
    push(RC);
    seg[v] = merge(seg[LC], seg[RC]);
}

void init(int i, Info x, int v=1, int l=0, int r=n) {
    push(v);
    if (r-l == 1) {
        seg[v] = x;
        return;
    }
    i<mid ? init(i,x, LC, l, mid) : init(i,x, RC, mid, r);
    pull(v);
}

void apply(int s, int e, int x, int v=1, int l=0, int r=n) {
    push(v);
    if (s<=l && r<=e) {
        chmax(seg[v].lz, x);
        push(v);
        return;
    }
    if (s<mid) apply(s, e, x, LC, l, mid);
    if (mid<e) apply(s, e, x, RC, mid, r);
    pull(v);
}

Info get(int s, int e, int v=1, int l=0, int r=n) {
    if (s<=l && r<=e) return seg[v];
    if (e<=mid) return get(s, e, LC, l, mid);
    if (mid<=s) return get(s, e, RC, mid, r);
    return merge(get(s, e, LC, l, mid), get(s, e, RC, mid, r));
}

void SOLVE() {
    cin >> n >> d;
    for (int i=0; i<n; i++) cin >> a[i];
    vector<int> f(n);
    {
        map<int, int> t;
        vector<int> all;
        for (int i=0; i<n; i++) all.pb(a[i]);
        UNIQUE(all);
        for (int i=0; i<all.size(); i++) t[all[i]] = i;
        for (int i=0; i<n; i++) {
            f[i] = t[a[i]];
            // cout << f[i] << sep;
        }
    }
    int ans = 0;
    for (int i=0; i<n; i++) {
        while (true) {
            Info res = get(0, n);
            // cout << res.mn << sep << res.pos << endl;
            if (res.mn == INF || i - res.mn <= d) break;
            init(res.pos, Info());
        }
        apply(f[i], n, i);
        int res = 1, tmp;
        if (0 < f[i]) res = get(0, f[i]).dp + 1, tmp = get(0, f[i]).mn; 
        init(f[i], Info(res, i, f[i], -1));
        chmax(ans, res);
        // cout << res << sep << tmp << endl;

    }
    cout << endl;
    cout << ans;
}   

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    FOR(T) SOLVE();
}

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