Submission #543049

#	Time	Username	Problem	Language	Result	Execution time	Memory
543049		SmolBrain	Financial Report (JOI21_financial)	C++17	100 / 100	682 ms	52412 KiB

Main

// Om Namah Shivaya
// GM in 127 days

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define endl '\n'
#define pb push_back
#define conts continue
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define ff first
#define ss second
#define ceil2(x,y) ((x+y-1) / (y))
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#ifndef ONLINE_JUDGE
#define debug(x) cout << #x <<" = "; print(x); cout << endl
#else
#define debug(x)
#endif

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

bool iseven(ll n) {if ((n & 1) == 0) return true; return false;}

void print(ll t) {cout << t;}
void print(int t) {cout << t;}
void print(string t) {cout << t;}
void print(char t) {cout << t;}
void print(double t) {cout << t;}
void print(ld t) {cout << t;}

template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(pair <T, V> p) {cout << "{"; print(p.ff); cout << ","; print(p.ss); cout << "}";}
template <class T> void print(vector <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T> void print(set <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T> void print(multiset <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T, class V> void print(map <T, V> v) {cout << "[ "; for (auto i : v) {print(i); cout << " ";} cout << "]";}
template<typename T> void amin(T &a, T b) { a = min(a, b); }
template<typename T> void amax(T &a, T b) { a = max(a, b); }

void usaco(string filename) {
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}

const int MOD = 1e9 + 7;
const int maxn = 1e5 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct lazysegtree {
    /*=======================================================*/

    struct data {
        ll a;
    };

    struct lazy {
        ll a;
    };

    data d_neutral = {0};
    lazy l_neutral = {0};

    void merge(data &curr, data &left, data &right) {
        curr.a = max(left.a, right.a);
    }

    void create(int x, int lx, int rx, T v) {
        tr[x].a = v;
    }

    void modify(int x, int lx, int rx, T v) {
        lz[x].a = v;
    }

    void propagate(int x, int lx, int rx) {
        ll val = lz[x].a;
        amax(tr[x].a, val);

        if (rx - lx > 1) {
            amax(lz[2 * x + 1].a, val);
            amax(lz[2 * x + 2].a, val);
        }

        lz[x] = l_neutral;
    }

    /*=======================================================*/

    int siz = 1;
    vector<data> tr;
    vector<lazy> lz;

    lazysegtree(int n) {
        while (siz < n) siz *= 2;
        tr.assign(2 * siz, d_neutral);
        lz.assign(2 * siz, l_neutral);
    }

    void build(vector<T> &a, int n, int x, int lx, int rx) {
        if (rx - lx == 1) {
            if (lx < n) {
                create(x, lx, rx, a[lx]);
            }

            return;
        }

        int mid = (lx + rx) / 2;

        build(a, n, 2 * x + 1, lx, mid);
        build(a, n, 2 * x + 2, mid, rx);

        merge(tr[x], tr[2 * x + 1], tr[2 * x + 2]);
    }

    void build(vector<T> &a, int n) {
        build(a, n, 0, 0, siz);
    }

    void rupd(int l, int r, T v, int x, int lx, int rx) {
        propagate(x, lx, rx);

        if (lx >= r or rx <= l) return;
        if (lx >= l and rx <= r) {
            modify(x, lx, rx, v);
            propagate(x, lx, rx);
            return;
        }

        int mid = (lx + rx) / 2;

        rupd(l, r, v, 2 * x + 1, lx, mid);
        rupd(l, r, v, 2 * x + 2, mid, rx);

        merge(tr[x], tr[2 * x + 1], tr[2 * x + 2]);
    }

    void rupd(int l, int r, T v) {
        rupd(l, r + 1, v, 0, 0, siz);
    }

    data query(int l, int r, int x, int lx, int rx) {
        propagate(x, lx, rx);

        if (lx >= r or rx <= l) return d_neutral;
        if (lx >= l and rx <= r) return tr[x];

        int mid = (lx + rx) / 2;

        data curr;
        data left = query(l, r, 2 * x + 1, lx, mid);
        data right = query(l, r, 2 * x + 2, mid, rx);

        merge(curr, left, right);
        return curr;
    }

    data query(int l, int r) {
        return query(l, r + 1, 0, 0, siz);
    }
};

struct DSU {
    // DSU data structure with 1-based indexing
    vector<int> par, rankk, mn, siz;

    DSU() {

    }

    DSU(int n) {
        init(n);
    }

    void init(int n) {
        par = vector<int>(n + 1);
        rankk = vector<int>(n + 1);
        mn = vector<int>(n + 1);
        siz = vector<int>(n + 1);
        rep1(i, n) create(i);
    }

    void create(int u) {
        par[u] = u;
        rankk[u] = 0;
        mn[u] = u;
        siz[u] = 1;
    }

    int find(int u) {
        if (u == par[u]) return u;
        else return par[u] = find(par[u]);
    }

    bool same(int u, int v) {
        return find(u) == find(v);
    }

    void merge(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;

        if (rankk[u] == rankk[v]) rankk[u]++;
        if (rankk[u] < rankk[v]) swap(u, v);

        par[v] = u;
        siz[u] += siz[v];
        amin(mn[u], mn[v]);
    }

    int getsz(int u) {
        return siz[find(u)];
    }

    int getmn(int u) {
        return mn[find(u)];
    }
};

void solve(int test_case)
{
    // https://codeforces.com/blog/entry/91295?#comment-801075
    // http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2021/financial/2021-open-financial-sol-en.pdf

    ll n, d; cin >> n >> d;
    vector<ll> a(n + 5);
    rep1(i, n) cin >> a[i];

    auto b = a;
    sort(all(b));
    auto it = unique(all(b));
    b.resize(it - b.begin());

    rep1(i, n) a[i] = lower_bound(all(b), a[i]) - a.begin();

    vector<pll> arr(n + 5);
    rep1(i, n) arr[i] = {a[i], -i};
    sort(arr.begin() + 1, arr.begin() + n + 1, greater<pll>());

    DSU dsu(n);
    set<ll> pos;
    vector<ll> rightmost(n + 5, n);

    rep1(x, n) {
        auto [val, i] = arr[x];
        i = -i;

        auto it = pos.upper_bound(i);
        if (it != pos.end()) {
            rightmost[i] = *it + d - 1;
        }

        if (i - 1 >= 1 and a[i - 1] >= a[i]) {
            dsu.merge(i, i - 1);
        }

        if (i + 1 <= n and a[i + 1] >= a[i]) {
            dsu.merge(i, i + 1);
        }

        if (dsu.getsz(i) >= d) {
            pos.insert(dsu.getmn(i));
        }
    }

    sort(arr.begin() + 1, arr.begin() + n + 1);

    lazysegtree<ll> st(n + 5);
    st.rupd(1, n, 1);

    vector<ll> dp(n + 5, 1);

    rep1(x, n) {
        auto [val, i] = arr[x];
        i = -i;

        dp[i] = st.query(i, i).a;
        st.rupd(i + 1, rightmost[i], dp[i] + 1);
    }

    ll ans = *max_element(all(dp));
    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;
    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void usaco(std::string)':
Main.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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