제출 #1150555

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150555		fatman87878	Financial Report (JOI21_financial)	C++20	19 / 100	199 ms	11100 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long

constexpr int maxN=3e5+5;

int n,N,d,segt[maxN<<1],tag[maxN];

pair<int,int> tagflag[maxN];

inline void upd(int pos,int tpos){
    if(tagflag[tpos].first)segt[pos] = tag[tpos];
    if(tagflag[tpos].second)segt[pos] = max(segt[pos],tag[tpos]);
    if(pos<n){
        if(tagflag[tpos].first)tag[pos]=tag[tpos];
        if(tagflag[tpos].second)tag[pos] = max(tag[pos],tag[tpos]);
        tagflag[pos].first|=tagflag[tpos].first;
        tagflag[pos].second|=tagflag[tpos].second;
    }
}

inline void push(int pos){
    pos+=n;
    for(int h = __lg(n);h;h--){
        int i = pos>>h;
        if(!i)continue;
        if(tagflag[i].first||tagflag[i].second)
            upd(i<<1,i),upd(i<<1|1,i),tagflag[i] = {0,0};
    }
}

inline void pull(int pos){
    for(pos+=n;pos>>=1;)if(!tagflag[pos].first&&!tagflag[pos].second){
        segt[pos] = max(segt[pos<<1],segt[pos<<1|1]);
    }
}

inline void ass(int _l,int _r,int tgw){
    push(_l),push(_r-1);
    tag[n+1] = tgw;
    tagflag[n+1] = {1,0};
    for(int l = _l+n,r = _r+n;l<r;l>>=1,r>>=1){
        if(l&1)upd(l++,n+1);
        if(r&1)upd(--r,n+1);
    }
    pull(_l),pull(_r-1);
}

inline void mdf(int _l,int _r,int tgw){
    push(_l),push(_r-1);
    tag[n+1] = tgw;
    tagflag[n+1] = {0,1};
    for(int l = _l+n,r = _r+n;l<r;l>>=1,r>>=1){
        if(l&1)upd(l++,n+1);
        if(r&1)upd(--r,n+1);
    }
    pull(_l),pull(_r-1);
}

inline int query(int l,int r){
    push(l),push(r-1);
    int ret = 0;
    for(l+=n,r+=n;l<r;l>>=1,r>>=1){
        if(l&1)ret = max(ret,segt[l++]);
        if(r&1)ret = max(ret,segt[--r]);
    }
    return ret;
}

vector<int> disc;

deque<pair<int,int>> dq;

int h[maxN];

int main(){
    IOS
    cin>>n>>d;
    for(int i = 1;i<=n;i++){
        cin>>h[i];
        disc.emplace_back(h[i]);
    }
    sort(all(disc));
    disc.erase(unique(all(disc)),disc.end());
    N=n;
    n=disc.size();
    for(int i = 1;i<=N;i++)h[i] = lower_bound(all(disc),h[i])-disc.begin();
    for(int i = 1;i<=N;i++){
        for(;!dq.empty()&&dq.back().first>h[i];dq.pop_back());
        dq.emplace_back(h[i],i);
        for(;!dq.empty()&&dq.front().second+d<i;dq.pop_front());
        if(i>d)ass(0,dq.front().first,-1e9);
        mdf(h[i],n,query(0,h[i])+1);
        if(i==N){
            cout<<query(0,n)<<'\n';
            return 0;
        }
    }
}

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