Submission #763026

#	Time	Username	Problem	Language	Result	Execution time	Memory
763026		anhduc2701	Financial Report (JOI21_financial)	C++17	100 / 100	627 ms	133000 KiB

Main

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e9;
const int maxn = 2e6 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, d;
int a[maxn];
int st[maxn];
multiset<int> q[maxn];
void build(int id, int l, int r)
{
    if (l == r)
    {
        st[id] = 0;
        return;
    }
    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    st[id] = max(st[id * 2], st[id * 2 + 1]);
}
void update(int id, int l, int r, int u, int val, int type)
{
    if (r < u || u < l)
    {
        return;
    }
    if (l == r)
    {
        if (type == 0)
        {
            q[id].erase(q[id].find(val));
        }
        if (type == 1)
        {
            q[id].insert(val);
        }
        if (q[id].empty())
            st[id] = 0;
        else
        {
            st[id] = (*q[id].rbegin());
        }
        return;
    }
    int mid = (l + r) / 2;
    update(id * 2, l, mid, u, val, type);
    update(id * 2 + 1, mid + 1, r, u, val, type);
    st[id] = max(st[id * 2], st[id * 2 + 1]);
}
int get(int id, int l, int r, int u, int v)
{
    if (v < 0)
        return 0;
    if (r < u || v < l)
        return 0;
    if (u <= l && r <= v)
    {
        return st[id];
    }
    int mid = (l + r) / 2;
    return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}
int dp[maxn];
vector<int> poi;
int last[maxn];
signed main()
{
    cin.tie(0), cout.tie(0)->sync_with_stdio(0);
    cin >> n >> d;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        poi.pb(a[i]);
    }
    sort(poi.begin(), poi.end());
    poi.resize(distance(poi.begin(), unique(poi.begin(), poi.end())));
    for (int i = 1; i <= n; i++)
    {
        a[i] = lower_bound(poi.begin(), poi.end(), a[i]) - poi.begin() + 1;
    }
    set<pair<int, int>> s;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        while (i - (-(*s.begin()).se) > d)
        {
            update(1, 1, poi.size(), (*s.begin()).fi, dp[-(*s.begin()).se], 0);

            s.erase(s.begin());
        }
        dp[i] = get(1, 1, poi.size(), 1, a[i] - 1) + 1;
        update(1, 1, poi.size(), a[i], dp[i], 1);
        ans = max(ans, dp[i]);
        s.insert({a[i], -i});
    }
    cout << ans;
}

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