Submission #577991

#	Time	Username	Problem	Language	Result	Execution time	Memory
577991		new_acc	Global Warming (CEOI18_glo)	C++14	100 / 100	984 ms	14124 KiB

glo

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct item{
    item *l,*r;
    int val,maxi,prior,key;
};
int t[N],dp1[N],dp2[N];
void comb(pitem v){
    v->maxi=max({v->val,(v->l!=nullptr?v->l->maxi:0),(v->r!=nullptr?v->r->maxi:0)});
}
pair<pitem,pitem> split(pitem v,int x){
    if(!v) return {nullptr,nullptr};
    if((v->key)<=x){
        pair<pitem,pitem> curr=split(v->r,x);
        v->r=curr.fi;
        comb(v);
        return {v,curr.se};
    }else{
        pair<pitem,pitem> curr=split(v->l,x);
        v->l=curr.se;
        comb(v);
        return {curr.fi,v};
    }
}
pitem merge(pitem v1,pitem v2){
    if(!v1 or !v2) return (!v1?v2:v1);
    if((v1->prior)>(v2->prior)){
        v1->r=merge(v1->r,v2);
        comb(v1);
        return v1;
    }else{
        v2->l=merge(v1,v2->l);
        comb(v2);
        return v2;
    }
}
pitem add(pitem v,int key,int x){
    pair<pitem,pitem>curr1=split(v,key);
    pair<pitem,pitem>curr2=split(curr1.fi,key-1);
    if(!curr2.se){
        pitem nn=new item;
        nn->l=nullptr,nn->r=nullptr,nn->val=x,nn->maxi=x,nn->key=key;
        nn->prior=uniform_int_distribution<int>(1,1000*1000*1000)(rng);
        return merge(merge(curr2.fi,nn),curr1.se);
    }
    curr2.se->val=max(curr2.se->val,x),curr2.se->maxi=max(curr2.se->maxi,x);
    return merge(merge(curr2.fi,curr2.se),curr1.se);
}
void clear(pitem v){
    if(!v) return;
    clear(v->l),clear(v->r);
    delete v;
}
void solve(){
    int n,d;
    cin>>n>>d;
    for(int i=1;i<=n;i++) cin>>t[i];
    pitem v=nullptr;
    for(int i=1;i<=n;i++){
        pair<pitem,pitem> s=split(v,t[i]-1);
        if(s.fi!=nullptr) dp1[i]=s.fi->maxi;
        dp1[i]++;
        v=merge(s.fi,s.se);
        v=add(v,t[i],dp1[i]);
    }    
    clear(v);
    v=nullptr;
    for(int i=n;i>=1;i--){
        pair<pitem,pitem> s=split(v,t[i]);
        if(s.se!=nullptr) dp2[i]=s.se->maxi;
        dp2[i]++;
        v=merge(s.fi,s.se);
        v=add(v,t[i],dp2[i]);
    }
    clear(v);
    v=nullptr;
    int res=0;
    for(int i=n;i>=1;i--){
        pair<pitem,pitem> curr1=split(v,t[i]-d);
        res=max(res,dp1[i]+(curr1.se!=nullptr?curr1.se->maxi:0));
        v=merge(curr1.fi,curr1.se);
        v=add(v,t[i],dp2[i]);
    }
    cout<<res<<"\n";
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}

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