Submission #1096733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096733		Wewoo	Global Warming (CEOI18_glo)	C++17	100 / 100	250 ms	13120 KiB

glo

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int,int> ii;
typedef pair <int,ii> iii;
typedef pair <int,iii> iiii;
//#define int ll
#define F first
#define S second
#define pb push_back
#define mp make_pair
bool BIT(int u,int v) {return (u&(1<<v));}
int gen(int l,int r)
{
    return l+(rand()%(r-l+1));
}
vector<int> rar;
int st[1600055][2];
int a[200005];
int x;
int n;
void upd(int id,int l,int r,int u,int t,int val)
{
    if (l==r) {st[id][t]=max(st[id][t],val);return;}
    int mid=(l+r)/2;
    if (mid>=u) upd(id*2,l,mid,u,t,val);
    else upd(id*2+1,mid+1,r,u,t,val);
    st[id][t]=max(st[id*2][t],st[id*2+1][t]);
}
int get(int id,int l,int r,int u,int v,int t)
{
    if (u>v) return 0;
    if (l>v||r<u) return 0;
    if (u<=l&&r<=v) return st[id][t];
    int mid=(l+r)/2;
    int g1=get(id*2,l,mid,u,v,t);
    int g2=get(id*2+1,mid+1,r,u,v,t);
    return max(g1,g2);
//    return max(get(id*2,l,mid,u,v,t),get(id*2+1,mid+1,r,u,v,t));
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(time(NULL));
 //   freopen("DAYDEP.inp","r",stdin);
  //  freopen("DAYDEP.out","w",stdout);
    cin>>n>>x;
    for(int i=1;i<=n;i++) cin>>a[i],rar.pb(a[i]),rar.pb(a[i]-x);
    sort(rar.begin(),rar.end());
    int res=0;
    for(int i=1;i<=n;i++)
    {
        int id=lower_bound(rar.begin(),rar.end(),a[i]-x)-rar.begin()+1;
        int dp0=1+get(1,1,2*n,1,id-1,0);
        res=max(res,dp0);
        int id1=lower_bound(rar.begin(),rar.end(),a[i])-rar.begin()+1;
        int dp1=1+max(get(1,1,2*n,1,id1-1,1),get(1,1,2*n,1,id1-1,0));
        res=max(res,dp1);
        upd(1,1,2*n,id1,1,dp1);
        upd(1,1,2*n,id,0,dp0);
    }
    cout<<res;
}

• 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