Submission #1126032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126032		AverageAmogusEnjoyer	Financial Report (JOI21_financial)	C++17	100 / 100	591 ms	42644 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> ui(0, 1 << 30);

int rng() { 
    return ui(mrand);
}

struct segment1 {
    int n;
    vector<pair<int,int>> st;
    int timer = 0;
    segment1(int N) {
        n = N;
        st.assign(4*n,make_pair(-1,-1));
    }
    pair<int,int> query(int p,int u,int tl,int tr) {
        if (tl == tr) 
            return st[u];
        int mid=(tl+tr)/2;
        if (p <= mid)
            return max(st[u],query(p,2*u,tl,mid));
        else
            return max(st[u],query(p,2*u+1,mid+1,tr));
    }
    int query(int p) {
        return query(p,1,0,n-1).second;
    }
    void upd(int l,int r,int x,int u,int tl,int tr) {
        if (l > r)
            return;
        if (l == tl && r == tr) {
            st[u]=make_pair(timer,x);
            return;
        }
        int mid=(tl+tr)/2;
        upd(l,min(mid,r),x,2*u,tl,mid);
        upd(max(mid+1,l),r,x,2*u+1,mid+1,tr);
    }
    void upd(int l,int r,int x) {
        upd(l,r,x,1,0,n-1);
        timer++;
    }
};

struct segment2 {
    int n;
    vector<int> st;
    segment2(int N) {
        n=N;
        st.resize(4*n);
    }
    int query(int l,int r,int u,int tl,int tr) {
        if (l > r)
            return 0;
        if (l == tl && r == tr)
            return st[u];
        int mid=(tl+tr)/2;
        return max(query(l,min(mid,r),2*u,tl,mid),query(max(mid+1,l),r,2*u+1,mid+1,tr));
    }
    int query(int l,int r) {
        return query(l,r,1,0,n-1);
    }
    void upd(int p,int x,int u,int tl,int tr) {
        if (tl == tr) {
            st[u]=x;
            return;
        }
        int mid=(tl+tr)/2;
        if (p <= mid)
            upd(p,x,2*u,tl,mid);
        else
            upd(p,x,2*u+1,mid+1,tr);
        st[u]=max(st[2*u],st[2*u+1]);
    }
    void upd(int p,int x) {
        upd(p,x,1,0,n-1);
    }
};

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);
    int n,k;
    cin >> n >> k;
    vector<int> a(n);
    vector<int> order(n);
    for (int i=0;i<n;i++)
        cin >> a[i];
    iota(order.begin(),order.end(),0);
    sort(order.begin(),order.end(),[&](int i,int j) {
        if (a[i]==a[j])
            return i < j;
        return a[i] < a[j];
    });
    // vector<int> L(n),R(n);
    // vector<int> dp(n);
    segment2 dp(n);
    segment1 L(n),R(n);
    auto Set = [&](segment1 &S,int l,int r,int x) {
        S.upd(l,r,x);
        // for (;l<=r;l++)
            // v[l]=x;
    };
    /*auto Max = [&](int l,int r) {
        int res=0;
        for (;l<=r;l++)
            cmax(res,dp[l]);
        return res;
    };*/
    set<int> active;
    for (int t=0,t2=0;t<n;t=t2) {
        vector<pair<int,int>> to_insert;
        while(t2 < n && a[order[t]] == a[order[t2]]) {
            int i=order[t2];
            t2++;
            if (active.empty()) {
                // L[i]=R[i]=i;
                L.upd(i,i,i);
                R.upd(i,i,i);
                to_insert.emplace_back(i,1);
                active.insert(i);
                continue;
            }
            auto it=active.lower_bound(i);
            if (it==active.end()) {
                --it;
                int bef=*it;
                if (bef < i - k) {
                    // L[i]=R[i]=i;
                    L.upd(i,i,i);
                    R.upd(i,i,i);
                    to_insert.emplace_back(i,1);
                } else {
                    int CL=L.query(bef),CR=i;
                    Set(R,CL,CR,CR);
                    Set(L,CL,CR,CL);
                    to_insert.emplace_back(i,dp.query(CL,i)+1);
                }
            } else {
                if (it!=active.begin()) {
                    auto it2=it; --it2;
                    int bef=*it2,aft=*it;
                    if (bef < i - k) {
                        if (aft > i + k) {
                            // L[i]=R[i]=i;
                            L.upd(i,i,i);
                            R.upd(i,i,i);
                            to_insert.emplace_back(i,1);
                        } else {
                            int CL=i,CR=R.query(aft);
                            Set(R,CL,CR,CR);
                            Set(L,CL,CR,CL);
                            to_insert.emplace_back(i,dp.query(CL,i)+1);
                        }
                    } else {
                        if (aft > i + k) {
                            int CL=L.query(bef),CR=i;
                            Set(R,CL,CR,CR);
                            Set(L,CL,CR,CL);
                            to_insert.emplace_back(i,dp.query(CL,i)+1);
                        } else {
                            int CL=L.query(bef),CR=R.query(aft);
                            Set(R,CL,CR,CR);
                            Set(L,CL,CR,CL);
                            to_insert.emplace_back(i,dp.query(CL,i)+1);
                        }
                    }
                } else {
                    int aft=*it;
                    if (aft > i + k) {
                        // L[i]=R[i]=i;
                        L.upd(i,i,i);
                        R.upd(i,i,i);
                        to_insert.emplace_back(i,1);
                    } else {
                        int CL=i,CR=R.query(aft);
                        Set(R,CL,CR,CR);
                        Set(L,CL,CR,CL);
                        to_insert.emplace_back(i,dp.query(CL,i)+1);
                    }
                }
            }
            active.insert(i);
        }
        for (auto &[p,x]: to_insert)
            dp.upd(p,x);
        to_insert.clear();
    }
    cout << dp.query(0,n-1) << endl;
}

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