Submission #1159312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159312		brinton	Financial Report (JOI21_financial)	C++20	100 / 100	102 ms	13384 KiB

Main

#include <bits/stdc++.h>
using namespace std;
struct SEG{
    private:
    vector<int> tree;// store range max
    vector<int> lazy;
    int N;
    void push(int idx,int l,int r){
        if(lazy[idx] == -1)return;
        if(l == r){
            lazy[idx] == -1;
            return;
        }
        tree[idx*2] = max(tree[idx*2],lazy[idx]);
        tree[idx*2+1] = max(tree[idx*2+1],lazy[idx]);
        lazy[idx*2] = max(lazy[idx*2],lazy[idx]);
        lazy[idx*2+1] = max(lazy[idx*2+1],lazy[idx]);
        lazy[idx] = -1;
    }
    void chMax(int l,int r,int idx,int L,int R,int nv){// maxWith nv
        // push lazy
        push(idx,l,r);
        if(L == l && r == R){
            tree[idx] = max(tree[idx],nv);
            lazy[idx] = nv;
            return;
        }
        int m = (l+r)/2;
        if(R <= m){
            chMax(l,m,idx*2,L,R,nv);
        }else if(L >= m+1){
            chMax(m+1,r,idx*2+1,L,R,nv);
        }else{
            chMax(l,m,idx*2,L,m,nv);
            chMax(m+1,r,idx*2+1,m+1,R,nv);
        }
        tree[idx] = max(tree[idx*2],tree[idx*2+1]);
    }
    void set(int l,int r,int idx,int tar,int nv){
        push(idx,l,r);
        if(l == r){
            tree[idx] = nv;
            lazy[idx] = -1;
            return;
        }
        int m = (l+r)/2;
        if(tar <= m){
            set(l,m,idx*2,tar,nv);
        }else{
            set(m+1,r,idx*2+1,tar,nv);
        }
        tree[idx] = max(tree[idx*2],tree[idx*2+1]);
    }
    int get(int l,int r,int idx,int lb){
        push(idx,l,r);
        if(l == r){
            return l;
        }
        int m = (l+r)/2;
        if(tree[idx*2] >= lb){
            return get(l,m,idx*2,lb);
        }else{
            return get(m+1,r,idx*2+1,lb);
        }
    }
    public:
    SEG(int iN){
        N = iN;
        tree = vector<int>(4*N+5,(int)(1e9+10));
        lazy = vector<int>(4*N+5,-1);
    }
    void chMax(int nv){
        chMax(0,N,1,0,N,nv);
    }
    void set(int tar,int nv){
        set(0,N,1,tar,nv);
    }
    int lower_bound(int lb){
        return get(0,N,1,lb);// range all
    }
};
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    //start here
    int N,D;
    cin >> N >> D;
    vector<int> v(N);
    for(auto &i:v)cin >> i;

    // what SEG do we need?
    /*
    1. range modify max;
    2. point set
    3. query to find lower_bound;
    */
    SEG LIS(N+1);
    deque<pair<int,int>> dq;// {val,idx}, val遞增，idx遞增
    for(int i = 0;i < N;i++){
        // set LIS to range min
        // change mustWalk to deque
        if(i != 0){// i == 0, dq is empty and there is nothing change
            while(dq.front().second < i-D)dq.pop_front();
            int mustWalk = dq.front().first;
            
            // range set max
            LIS.chMax(mustWalk);
            // for(auto &j:LIS){
            //     j = max(j,mustWalk);
            // }
        }
        int it = LIS.lower_bound(v[i]);
        LIS.set(it,v[i]);
        // for(auto i:LIS)cout << i << " ";cout << endl;

        // push cur to deque
        while(!dq.empty() && dq.back().first >= v[i]) dq.pop_back();
        dq.push_back({v[i],i});
    }
    cout << LIS.lower_bound((int)(1e9+5));
}

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