Submission #423464

#	Time	Username	Problem	Language	Result	Execution time	Memory
423464		qwerasdfzxcl	Financial Report (JOI21_financial)	C++14	100 / 100	1967 ms	180496 KiB

Main

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
int a[300300], dp[300300];
struct Seg1{
    vector<int> tree; int sz;
    void init(int n){
        sz = n;
        tree.resize(n*2);
    }
    void init2(int n, int* b){
        sz = n;
        tree.resize(n*2);
        for (int i=sz;i<sz*2;i++) tree[i] = b[i-sz];
        for (int i=sz-1;i;i--) tree[i] = max(tree[i<<1], tree[i<<1|1]);
    }
    void update(int p, int x){
        for (tree[p+=sz]=x;p>1;p>>=1) tree[p>>1] = max(tree[p], tree[p^1]);
    }
    int query(int l, int r = -1){
        int ret = 0;
        if (r==-1) r = sz;
        for (l += sz, r += sz;l<r;l>>=1, r>>=1){
            if (l&1) ret = max(ret, tree[l++]);
            if (r&1) ret = max(tree[--r], ret);
        }
        return ret;
    }
}TREE3;
struct MST{
    vector<pair<int, int>> tree[600600];
    Seg1 tree2[600600];
    int sz;
    int sp[300300][20], h[600600];
    void init(int n){
        sz = n;
        for (int i=sz;i<sz*2;i++){
            tree[i] = {make_pair(a[i-sz], i-sz)};
            tree2[i].init(tree[i].size());
            sp[i-sz][0] = 0;
        }
        for (int i=sz-1;i;i--){
            tree[i].resize(tree[i<<1].size()+tree[i<<1|1].size());
            merge(tree[i<<1].begin(), tree[i<<1].end(), tree[i<<1|1].begin(), tree[i<<1|1].end(), tree[i].begin());
            tree2[i].init(tree[i].size());
            h[i] = max(h[i<<1], h[i<<1|1])+1;
            for (int j=0;j<(int)tree[i].size();j++) sp[tree[i][j].second][h[i]] = j;
        }
    }
    void update(int p, int val){
        int x = p;
        for (p += sz;p;p>>=1){
            tree2[p].update(sp[x][h[p]], val);
        }
    }
    int query(int l, int r, int x){
        pair<int, int> p = make_pair(x, 1e9);
        int ret = 0;
        for (l += sz, r += sz;l<r;l>>=1, r>>=1){
            if (l&1){
                int idx = upper_bound(tree[l].begin(), tree[l].end(), p)-tree[l].begin();
                ret = max(ret, tree2[l].query(idx));
                l++;
            }
            if (r&1){
                --r;
                int idx = upper_bound(tree[r].begin(), tree[r].end(), p)-tree[r].begin();
                ret = max(ret, tree2[r].query(idx));
            }
        }
        return ret;
    }
}TREE1;

int b[300300];
struct MinSeg{
    int tree[600600], sz;
    void init(int n){
        sz = n;
        for (int i=sz;i<sz*2;i++) tree[i] = a[i-sz];
        for (int i=sz-1;i;i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
    }
    int query(int l, int r){
        int ret = 1e9;
        for (l += sz, r += sz;l<r;l>>=1, r>>=1){
            if (l&1) ret = min(ret, tree[l++]);
            if (r&1) ret = min(ret, tree[--r]);
        }
        return ret;
    }
}TREE2;

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    for (int i=0;i<n;i++) cin >> a[i];
    TREE1.init(n);
    TREE2.init(n);
    for (int i=0;i<n-k+1;i++) b[i] = TREE2.query(i, i+k);
    TREE3.init2(n-k+1, b);

    int ans = 1;
    for (int i=n-1;i>=0;i--){
        int l = i+1, r = n-k+1, idx = i;
        while(l<r){
            int m = (l+r)>>1;
            int tmp = TREE3.query(i, m+1);
            if (tmp>a[i]) r = m;
            else l = m+1, idx = m;
        }
        idx = min(idx+k, n-1);
        dp[i] = TREE1.query(i+1, idx+1, a[i])+1;
        TREE1.update(i, dp[i]);
        ans = max(ans, dp[i]);
    }
    cout << ans;

    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