Submission #536352

#	Time	Username	Problem	Language	Result	Execution time	Memory
536352		sare	Financial Report (JOI21_financial)	C++17	100 / 100	594 ms	27528 KiB

Main

//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;
string to_string(char c) { return string(1,c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
template<class A> string to_string(complex<A> c) { 
    stringstream ss; ss << c; return ss.str(); }
string to_string(vector<bool> v) { 
    string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]);
    res += "}"; return res; }
template<size_t SZ> string to_string(bitset<SZ> b) {
    string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]);
    return res; }
template<class A, class B> string to_string(pair<A,B> p);
template<class T> string to_string(T v) { // containers with begin(), end()
    bool fst = 1; string res = "{";
    for (const auto& x: v) {
        if (!fst) res += ", ";
        fst = 0; res += to_string(x);
    }
    res += "}"; return res;
}
template<class A, class B> string to_string(pair<A,B> p) {
    return "("+to_string(p.first)+", "+to_string(p.second)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
    DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
#else
#define wis(...) 0
#endif
typedef long long ll;
typedef long double ld;
#define all(x) (x).begin(), (x).end()
const int MAXN = 3e5 + 10;
int n, d, a[MAXN], L[MAXN], dp[MAXN];
pair<int, int> p[MAXN];

struct SegTree {
    int seg[MAXN << 2];

    void set (int nd, int cl, int cr, int ind, int val) {
        if (cr - cl == 1) {
            seg[nd] = val;
            return;
        }
        int lc = nd << 1, rc = lc | 1, mid = (cl + cr) >> 1;
        if (ind < mid) {
            set(lc, cl, mid, ind, val);
        }
        else {
            set(rc, mid, cr, ind, val);
        }
        seg[nd] = max(seg[lc], seg[rc]);
    }
    inline void set (int ind, int val) {
        set(1, 0, n, ind, val);
    }

    int get (int nd, int cl, int cr, int l, int r) {
        if (cl == l && cr == r) {
            return seg[nd];
        }
        int lc = nd << 1, rc = lc | 1, mid = (cl + cr) >> 1, res = 0;
        if (l < mid) {
            res = max(res, get(lc, cl, mid, l, min(mid, r)));
        }
        if (r > mid) {
            res = max(res, get(rc, mid, cr, max(mid, l), r));
        }
        return res;
    }
    inline int get (int l, int r) {
        return get(1, 0, n, l, r);
    }
} seg;

inline int get (int v) {
    return L[v] == v ? v : L[v] = get(L[v]);
}

int main() {
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> d;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        p[i] = {a[i], -i};
    }
    sort(p, p + n);

    set<int> cur;
    for (int i = 0; i < n; ++i) {
        int ind = -p[i].second;
        if (cur.empty() || ind < *cur.begin()) {
            L[ind] = ind;
            dp[ind] = 1;
            cur.insert(ind);
        }
        else {
            auto it = --cur.lower_bound(ind);
            if (ind - *it <= d) {
                L[ind] = get(*it);
            }
            else {
                L[ind] = ind;
            }
            dp[ind] = seg.get(L[ind], ind) + 1;
        }
        cur.insert(ind);
        seg.set(ind, dp[ind]);

        auto it = cur.upper_bound(ind);
        if (it != cur.end() && *it - ind <= d) {
            L[*it] = L[ind];
        }
    }
    cout << seg.seg[1] << '\n';
}

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