Submission #1143781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143781		owoovo	Financial Report (JOI21_financial)	C++20	100 / 100	251 ms	13256 KiB

Main

#include<bits/stdc++.h>
#define ll long long 
#define lc id*2+1
#define rc id*2+2
#define F first 
#define S second 
using namespace std;
int val[1200010],tag[1200010];
void build(int l,int r,int id){
    tag[id]=-1;
    if(l==r)return;
    int m=(l+r)>>1;
    build(l,m,lc);
    build(m+1,r,rc);
}
void addtag(int id,int v){
    tag[id]=v;
    val[id]=v;
}
void push(int id){
    if(tag[id]!=-1){
        addtag(lc,tag[id]);
        addtag(rc,tag[id]);
        tag[id]=-1;
    }
}
void modify(int l,int r,int id,int L,int R,int v){
    if(L>R)return;
    if(l==L&&r==R){
        addtag(id,v);
        return;
    }
    push(id);
    int m=(l+r)>>1;
    if(R<=m){
        modify(l,m,lc,L,R,v);
    }else if(L>m){
        modify(m+1,r,rc,L,R,v);
    }else{
        modify(l,m,lc,L,m,v);
        modify(m+1,r,rc,m+1,R,v);
    }
    val[id]=max(val[lc],val[rc]);
}
int query(int l,int r,int id,int L,int R){
    if(L>R)return 0;
    if(l==L&&r==R){
        return val[id];
    }
    push(id);
    int m=(l+r)>>1;
    if(R<=m){
        return query(l,m,lc,L,R);
    }else if(L>m){
        return query(m+1,r,rc,L,R);
    }else{
        return max(query(l,m,lc,L,m),query(m+1,r,rc,m+1,R));
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,d;
    cin>>n>>d;
    vector<int> v,use;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        v.push_back(a);
        use.push_back(a);
    }
    sort(use.begin(),use.end());
    use.erase(unique(use.begin(),use.end()),use.end());
    int sz=use.size();
    for(int i=0;i<n;i++){
        v[i]=lower_bound(use.begin(),use.end(),v[i])-use.begin()+1;
    }
    build(1,sz,0);
    deque<pair<int,int>> qu;
    qu.push_back({0,v[0]});
    modify(1,sz,0,v[0],v[0],1);
    for(int i=1;i<n;i++){
        int best=max(query(1,sz,0,1,v[i]-1)+1,query(1,sz,0,v[i],v[i]));
        modify(1,sz,0,v[i],v[i],best);
        while(!qu.empty()&&i-qu.front().F>=d)qu.pop_front();
        while(!qu.empty()&&qu.back().S>=v[i])qu.pop_back();
        qu.push_back({i,v[i]});
        modify(1,sz,0,1,qu.front().S-1,0);
    }
    cout<<query(1,sz,0,1,sz)<<"\n";
    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