Submission #1072690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072690		boyliguanhan	Global Warming (CEOI18_glo)	C++17	48 / 100	2064 ms	120772 KiB

glo

#include<bits/stdc++.h>
using namespace std;
struct {
    map<int,int>mp;
    int query(int pos){
        int ans=0;
        while(pos)
            ans=max(ans,mp[pos]),
            pos-=pos&-pos;
        return ans;
    }
    void upd(int pos,int x){
        while(pos<=1e9)
            mp[pos]=max(mp[pos],x),
            pos+=pos&-pos;
    }
    void reset(){
        mp.clear();
    }  
} BIT;
int goleft[200100], goright[200100], vl[200100];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,x;
    cin>>n>>x;
    for(int i=1;i<=n;i++){ cin>>vl[i];
        goleft[i]=BIT.query(vl[i]-1)+1;
        BIT.upd(vl[i],goleft[i]);
    }
    BIT.reset();
    for(int i=n;i;i--){
        goright[i]=BIT.query(1e9-vl[i])+1;
        BIT.upd(1e9-vl[i]+1,goright[i]);
    }
    int ans=0;
    BIT.reset();
    for(int i=1;i<=n;i++){
        ans=max(ans,goright[i]+BIT.query(vl[i]+x-1));
        BIT.upd(vl[i],goleft[i]);
    }
    cout<<ans<<'\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 0 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25