Submission #679783

#	Time	Username	Problem	Language	Result	Execution time	Memory
679783		bashkort	Financial Report (JOI21_financial)	C++17	100 / 100	335 ms	12920 KiB

Main

//#define _GLIBCXX_DEBUG

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

using namespace std;


#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

#define ll long long
#define trace(x) cout << #x << " = " << (x) << endl;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define uniq(x) x.resize(unique(all(x)) -  begin(x))
#define ld long double
#define sz(s) (int) size(s)
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define mt make_tuple
#define int128 __int128

template<typename T>
bool ckmn(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<typename T>
bool ckmx(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

int bit(int x, int b) {
    return (x >> b) & 1;
}


int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }

const ll infL = 3e18;
const int infI = 1e9 + 7;
const int N = 300000;
const ll mod = 998244353;
const ld eps = 1e-9;

vector<int> t;
int sz = 1;

void init(int n) {
    while (sz < n) sz <<= 1;
    t.resize(sz << 1);
    fill(all(t), -infI);
}

void Set(int i, int v) {
    int x = i + sz;
    while (x) {
        ckmx(t[x], v);
        x >>= 1;
    }
}

int get(int l, int r, int x = 1, int lx = 0, int rx = sz) {
    if (l >= rx || lx >= r) return -infI;
    if (l <= lx && rx <= r) return t[x];
    int m = (lx + rx) >> 1;
    return max(get(l, r, x << 1, lx, m), get(l, r, x << 1 | 1, m, rx));
}


int n, d;

set <pair<int, int>> st; //l, r
int get(int x) {
    auto it = st.upper_bound(mp(x, infI));
    if (it == st.begin()) return 0;
    it = prev(it);
    auto[L, R] = *it;
    if (R < x) {
        return R - d + 1;
    }
    if (x - L >= d) return x - d;
    else {
        if (it == st.begin()) return 0;
        else {
            it = prev(it);
            auto [l, r] = *it;
            int y = r - d + 1;
            assert(l <= y && y <= r);
            assert(0 <= y);
            return y;
        }
    }
}

void del(int x) {
    auto it = st.upper_bound(mp(x, infI));
    if (it == st.begin()) return;
    assert(it != st.begin());
    it = prev(it);
    auto[L, R] = *it;
    if (R < x) return;
    st.erase(it);
    int RR = x - 1, LL = x + 1;
    if (RR - L + 1 >= d) st.insert(mp(L, RR));
    if (R - LL + 1 >= d) st.insert(mp(LL, R));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> d;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector<int> yy = a;
    sort(all(yy));
    uniq(yy);
    for (int i = 0; i < n; ++i) a[i] = lower_bound(all(yy), a[i]) - begin(yy);
    vector<int> ord(n);
    iota(all(ord), 0);
    sort(all(ord), [&a](int i, int j) { return a[i] < a[j]; });
    if (d == 1) {
        vector<int> ans(n);
        vector<int> st;
        for (int i = n - 1; i > -1; --i) {
            while (!st.empty() && a[st.back()] <= a[i]) st.pop_back();
            if (st.empty()) ans[i] = 1;
            else ans[i] = ans[st.back()] + 1;
            st.push_back(i);
        }
        cout << *max_element(all(ans));
    } else if (d == n) {
        init(n);
        for (int i = 0; i < n; ++i) {
            int mx = max(0, get(0, a[i])) + 1;
            Set(a[i], mx);
        }
        cout << t[1];
        return 0;
    } else {
        init(n);
        st.insert(mp(0, n - 1));
        //r, l
        for (int idx = 0; idx < n;) {
            vector<int> now;
            int J = idx;
            while (J < n && a[ord[J]] == a[ord[idx]]) {
//                trace(a[ord[J]])

                now.push_back(ord[J]);
                ++J;
            }
            idx = J;
            vector<int> ans;
            for (int i : now) {
                int l = get(i);
                ans.push_back(max(0, get(l, i)) + 1);
            }
            for (int j = 0; j < sz(now); ++j) {
                int i = now[j];
                Set(i, ans[j]);
                del(i);
            }
        }
        cout << t[1];
    }
    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