Submission #440811

#	Time	Username	Problem	Language	Result	Execution time	Memory
440811		den_tar	Global Warming (CEOI18_glo)	C++14	100 / 100	190 ms	10124 KiB

glo

#include <bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio();cin.tie();cout.tie();
#define en cout<<endl;
#define ops cout<<"ops"<<endl;
#define line cout<<"---------------------------"<<endl;
#define fi first
#define se second

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pllll;
typedef string str;

const ll DIM = 2e5 + 7;
const ll DIMM = 5e4 + 7;
const ll DDIM = 7;
const ll INF = 1e18 + 7;
const ll X = 1e5 + 7;
const ll BS = 2e5 + 7;
const ll AS = 26 + 7;
const ll MODULO = 1e9 + 7;

ll nt,n,m,k,q;

ll a[DIM];

ll d1[DIM],d2[DIM],pos[DIM],pr[DIM];

ll l,r,mid;

ll l1;

ll res;

int main()
{
    fast;
    //ll x1,y1,x2,y2;

    cin>>n>>m;

    for(int i=1;i<=n;i++)cin>>a[i];





    d1[0]=(-INF);
    d2[0]=INF;

    for(int i=1;i<=n;i++){
     d1[i]=INF;
     d2[i]=(-INF);
    }






    for(int i=1;i<=n;i++){

     l=0;r=i-1;

     while(l<r){
      mid=(l+r+1)/2;
      if(d1[mid]<a[i])l=mid;
      else r=mid-1;
     }

     pos[i]=l+1;
     pr[i]=d1[l+1];

     d1[l+1]=a[i];

    }




    res=(-INF);

    for(ll i=1;i<=n;i++)
     if(d1[i]!=INF)res=max(res,i);







    if(m==0){
     cout<<res<<endl;
     return 0;
    }





    for(int i=n;i>=1;i--){

     d1[pos[i]]=pr[i];

     a[i]+=m;

     l=0;r=n-i;

     while(l<r){
      mid=(l+r+1)/2;
      if(d2[mid]>a[i])l=mid;
      else r=mid-1;
     }

     if(d2[l]>a[i] && a[i]>d2[l+1])d2[l+1]=a[i];

     l1=l+1;

     l=0;r=i-1;

     while(l<r){
      mid=(l+r+1)/2;
      if(d1[mid]<a[i])l=mid;
      else r=mid-1;
     }

     res=max(res,(l1+l));
    }

    cout<<res<<endl;

    return 0;
}

• 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