Submission #603677

#	Time	Username	Problem	Language	Result	Execution time	Memory
603677		AA_Surely	Financial Report (JOI21_financial)	C++17	100 / 100	763 ms	32296 KiB

Main

#include <bits/stdc++.h>

#define FOR(i, x, n) for(int i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(int i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)

#define WTF cout << "WTF" << endl

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
#define PB push_back

#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;

const int N = 3e5 + 7;
const int INF = 1e9 + 7;

#define lc now << 1
#define rc now << 1 | 1

int n, d;
PII ns[N];
set<int> keep;

struct LzTree {
    int tree[N << 2], lz[N << 2];

    inline void shift(int now) {
        tree[lc] += lz[now];
        lz[lc] += lz[now];

        tree[rc] += lz[now];
        lz[rc] += lz[now];

        lz[now] = 0;
        return;
    }

    void add(int lq, int rq, int val, int now = 1, int ls = 0, int rs = n - 1) {
        if (rq < lq || rq < ls || rs < lq) return;
        if (lq <= ls && rs <= rq) {
            tree[now] += val;
            lz[now] += val;
            return;
        }

        int mid = (ls + rs) >> 1;
        shift(now);
        add(lq, rq, val, lc, ls, mid);
        add(lq, rq, val, rc, mid + 1, rs);

        tree[now] = max(tree[lc], tree[rc]);
        return;
    }

    int get(int id, int now = 1, int ls = 0, int rs = n - 1) {
        if (ls == rs) return tree[now];
        int mid = (ls + rs) >> 1;
        shift(now);
        if (id <= mid) return get(id, lc, ls, mid);
        return get(id, rc, mid + 1, rs);
    }

    int rightest(int q, int val, int now = 1, int ls = 0, int rs = n - 1) {
        if (ls >= q || tree[now] < val) return -1;
        if (ls == rs) return ls;
        shift(now);
        int mid = (ls + rs) >> 1;
        int case1 = rightest(q, val, rc, mid + 1, rs);
        return (case1 == -1 ? rightest(q, val, lc, ls, mid) : case1);
    }
} dist;

struct NorTree {
    int tree[N << 2];

    void change(int id, int val, int now = 1, int ls = 0, int rs = n - 1) {
        if (ls == rs) {
            tree[now] = val;
            return;
        }

        int mid = (ls + rs) >> 1;
        if (id <= mid) change(id, val, lc, ls, mid);
        else change(id, val, rc, mid + 1, rs);

        tree[now] = max(tree[lc], tree[rc]);
        return;
    }

    int get(int lq, int rq, int now = 1, int ls = 0, int rs = n - 1) {
        if (rq < lq || rq < ls || rs < lq) return 0;
        if (lq <= ls && rs <= rq) return tree[now];
        int mid = (ls + rs) >> 1;
        return max(get(lq, rq, lc, ls, mid), get(lq, rq, rc, mid + 1, rs));
    }
} dp;

inline bool comp(const PII &a, const PII &b) {
    if (a.F != b.F) return a.F < b.F;
    return a.S > b.S;
}

int main() {
    IOS;

    cin >> n >> d;
    int cnt = n;
    F0R(i, n) {
        cin >> ns[i].F;
        ns[i].S = i;

        dist.add(i, i, cnt);
        cnt--;
    }

    /*cout << "dists are " << endl;
    F0R(i, n) cout << dist.get(i) << ' '; cout << endl;*/

    sort(ns, ns + n, comp);
    keep.insert(0);
    
    int pr = 0;
    F0R(i, n) {
        int ans = 1;
        int pl = *(--keep.lower_bound(ns[i].S));
        int x = dist.get(ns[i].S);
        dist.add(pl, ns[i].S - 1, -x);

        int f = dist.rightest(ns[i].S, d + 1);
        //cout << "f = " << f << endl;

        ans = max(ans, dp.get(f + 1, ns[i].S) + 1);
        //cout << "ans is " << ans << endl;

        pr = max(pr, ans);
        dp.change(ns[i].S, ans);
        keep.insert(ns[i].S);
    
        /*cout << "after adding " << ns[i].S + 1 << "'th number, dists are " << endl;
        F0R(i, n) cout << dist.get(i) << ' '; cout << endl;

        cout << "and dp's are : ";
        F0R(i, n) cout << dp.get(i, i) << ' '; cout << endl;*/
    }
    
    cout << pr;
}

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