제출 #1243917

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243917		erering	Financial Report (JOI21_financial)	C++20	100 / 100	690 ms	160100 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define endl '\n'
using namespace std;
const int N=3e5+5,inf=2e18,MOD=1e9+9;
int seg[N*4][3],offset=1,dp[N];
void update(int idx,int val,int t){
    idx+=offset;
    seg[idx][t]=val;
    idx/=2;
    while(idx>0){
        seg[idx][t]=min(seg[idx*2][t],seg[idx*2+1][t]);
        idx/=2;
    }
}
int query(int node,int qlo,int qhi,int lo,int hi,int t){
    if(lo>=qlo && hi<=qhi)return seg[node][t];
    if(lo>qhi || hi<qlo)return inf;
    int mid=(lo+hi)/2;
    return min(query(node*2,qlo,qhi,lo,mid,t),query(node*2+1,qlo,qhi,mid+1,hi,t));
}
set<int> sols[N*4];
void update2(int idx){
    auto it=sols[idx].end();
    it--;
    idx+=offset;
    seg[idx][2]=*it;
    idx/=2;
    while(idx>0){
        seg[idx][2]=max(seg[idx*2][2],seg[idx*2+1][2]);
        idx/=2;
    }
}
int query2(int node,int qlo,int qhi,int lo,int hi){
    if(lo>=qlo && hi<=qhi)return seg[node][2];
    if(lo>qhi || hi<qlo)return -inf;
    int mid=(lo+hi)/2;
    return max(query2(node*2,qlo,qhi,lo,mid),query2(node*2+1,qlo,qhi,mid+1,hi));
}
vector<int> rem[N]; //at time i remove these dp values because u cant take them anymore
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    for(int i=0;i<N*4;i++){
        for(int j=0;j<2;j++)seg[i][j]=inf;
    }
    int n,d; cin>>n>>d;
    while(offset<n)offset*=2;
    int a[n];
    set<int> comp;
    for(int i=0;i<n;i++){
        cin>>a[i];
        comp.insert(a[i]);
    }
    map<int,int> id;
    int cnt=0;
    for(auto i:comp)id[i]=cnt++;
    for(int i=0;i<n;i++){
        a[i]=id[a[i]];
        update(i,a[i],0);
        sols[a[i]].insert(0);
    }
    vector<int> pos;
    for(int i=n-1;i>n-d-1;i--)pos.pb(i);
    for(int i=n-d-1;i>=0;i--){
        int whn=query(1,a[i]+1,offset-1,0,offset-1,1);
        if(whn!=inf)rem[whn].pb(i);
        else pos.pb(i);
        int mn=query(1,i,i+d-1,0,offset-1,0);
        update(mn,i+d,1);
    }
    for(int i=0;i<n;i++){
        for(auto j:rem[i]){
            sols[a[j]].extract(dp[j]);
            update2(a[j]);
        }
        dp[i]=1;
        if(a[i]>0)dp[i]=query2(1,0,a[i]-1,0,offset-1)+1;
        sols[a[i]].insert(dp[i]);
        update2(a[i]);
    }
    int ans=0;
    for(auto i:pos){
        ans=max(ans,dp[i]);
     //   cout<<i+1<<' '<<dp[i]<<endl;
    }
    cout<<ans;
}

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