Submission #647956

#	Time	Username	Problem	Language	Result	Execution time	Memory
647956		BackNoob	Financial Report (JOI21_financial)	C++14	100 / 100	589 ms	53288 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
 
using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}

int lim;

struct IT{
    struct Node{
        int pre;
        int suf;
        int le;
        int mx;
    };
    int n;
    vector<Node> t;
    IT(){}
    IT(int _n) {
        n = _n;
        t.resize(n * 4 + 7, {0, 0, 0, 0});
    }

    Node union_node(Node &a, Node &b)
    {
        Node res;
        if(a.le == 0) {
            res = b;
            return res;
        }
        if(b.le == 0) {
            res = a;
            return res;
        }
        res.le = a.le + b.le;
        res.pre = a.pre;
        if(a.pre == a.le) res.pre = a.pre + b.pre;
        res.suf = b.suf;
        if(b.suf == b.le) res.suf = b.suf + a.suf;
        res.mx = max({a.mx, b.mx, a.suf + b.pre});
        return res;
    }

    void build(int v, int tl, int tr)
    {
        if(tl == tr) t[v] = {0, 0, 1, 0};
        else {
            int tm = (tl + tr) / 2;
            build(v * 2, tl, tm);
            build(v * 2 + 1, tm + 1, tr);
            t[v] = union_node(t[v * 2], t[v * 2 + 1]);
        }
    }

    void update(int v, int tl, int tr, int pos, int val)
    {
        if(tl == tr) t[v] = {1, 1, 1, 1};
        else {
            int tm = (tl + tr) / 2;
            if(pos <= tm) update(v * 2, tl, tm, pos, val);
            else update(v * 2 + 1, tm + 1, tr, pos, val);
            t[v] = union_node(t[v * 2], t[v * 2 + 1]);
        }
    }

    void update(int pos, int val)
    {
        update(1, 1, n, pos, val);
    }

    void findpos(int v, int tl, int tr, int l, int r, int &res, Node &cur)
    {
        if(l > r) return;
        if(tl == l && tr == r) {
            Node newcur = union_node(cur, t[v]);
            if(newcur.mx < lim) {
                swap(cur, newcur);
                maximize(res, r);
                return;
            }
        }
        if(tl == tr) return;
        int tm = (tl + tr) / 2;
        findpos(v * 2, tl, tm, l, min(r, tm), res, cur);
        if(res >= tm) 
            findpos(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, res, cur);
    }

    int findpos(int l, int r)
    {
        Node cur = {0, 0, 0, 0};
        int res = l - 1;
        findpos(1, 1, n, l, r, res, cur);
        return res + 1;
    }

} seg;


struct ITMAX{
    int n;
    vector<int> t;
    ITMAX(){}
    ITMAX(int _n) {
        n = _n;
        t.resize(n * 4 + 7, 0);
    }

    void update(int v, int tl, int tr, int pos, int val)
    {
        if(tl == tr) t[v] = val;
        else {
            int tm = (tl + tr) / 2;
            if(pos <= tm) update(v * 2, tl, tm, pos, val);
            else update(v * 2 + 1, tm + 1, tr, pos, val);
            t[v] = max(t[v * 2], t[v * 2 + 1]);
        }
    }

    int getmax(int v, int tl, int tr, int l, int r)
    {
        if(l > r) return 0;
        if(tl == l && tr == r) return t[v];
        int tm = (tl + tr) / 2;
        int m1 = getmax(v * 2, tl, tm, l, min(r, tm));
        int m2 = getmax(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
        return max(m1, m2);
    }

    void update(int pos, int val)
    {
        update(1, 1, n, pos, val);
    }
    int getmax(int l, int r)
    {
        return getmax(1, 1, n, l, r);
    }
} segmax;


 
int n;
int cnt[mxN];
int a[mxN];
int dp[mxN];
int rig[mxN];
vector<int> order[mxN];
 
void solve()
{
    cin >> n >> lim;
    for(int i = 1; i <= n; i++) cin >> a[i];

    vector<int> cp;
    for(int i = 1; i <= n; i++) cp.pb(a[i]);
    sort(all(cp));
    
    vector<pair<int, int>> val;
    for(int i = 1; i <= n; i++) val.pb({-a[i], i});
    sort(all(val));
    
    seg = IT(n);
    seg.build(1, 1, n);
    segmax = ITMAX(n);

    for(int i = 0; i < sz(val); i++) {
        int j = i;
        while(j < sz(val) && val[j].fi == val[i].fi) ++j;

        for(int k = i; k < j; k++) {
            rig[val[k].se] = seg.findpos(val[k].se + 1, n);
        }

        for(int k = i; k < j; k++) {
            seg.update(val[k].se, 1);
        }

        i = j - 1;
    }

    // for(int i = 1; i <= n; i++) cout << rig[i] << ' ';
    // cout << endl;


    for(int i = 1; i <= n; i++) {
        a[i] = lower_bound(all(cp), a[i]) - cp.begin() + 1;
        cnt[a[i]]++;
        a[i] += cnt[a[i]] - 1;
    }
    for(int i = 1; i <= n; i++) order[rig[i] + 1].pb(i);

    for(int i = 1; i <= n; i++) {
        for(auto it : order[i]) {
            segmax.update(a[it], 0);
        }

        dp[i] = 1;
        int p = lower_bound(all(cp), cp[a[i] - 1]) - cp.begin();
        maximize(dp[i], segmax.getmax(1, p) + 1);

        segmax.update(a[i], dp[i]);
    }

    int res = 0;
    for(int i = 1; i <= n; i++) maximize(res, dp[i]);
    cout << res;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(TASK".inp" , "r" , stdin);
    //freopen(TASK".out" , "w" , stdout);
 
    int tc = 1;
    //cin >> tc;
    while(tc--) {
        solve();
    }
    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