Submission #504240

#	Time	Username	Problem	Language	Result	Execution time	Memory
504240		ToroTN	Global Warming (CEOI18_glo)	C++14	100 / 100	85 ms	6208 KiB

glo

#include<bits/stdc++.h>
using namespace std;
int n,d,a[200005],b[200005],dp1[200005],dp2[200005],mx=-1;
vector<int> v1,v2;
int main()
{
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=-a[i];
        if(lower_bound(v1.begin(),v1.end(),a[i])==v1.end())
        {
            v1.push_back(a[i]);
        }else
        {
            v1[lower_bound(v1.begin(),v1.end(),a[i])-v1.begin()]=a[i];
        }
        dp1[i]=lower_bound(v1.begin(),v1.end(),a[i])-v1.begin()+1;
        //printf("%d ",dp1[i]);
    }
    //printf("\n");
    for(int i=n;i>=1;i--)
    {
        dp2[i]=lower_bound(v2.begin(),v2.end(),b[i])-v2.begin()+1;
        if(lower_bound(v2.begin(),v2.end(),b[i]-d)==v2.end())
        {
            v2.push_back(b[i]-d);
        }else
        {
            v2[lower_bound(v2.begin(),v2.end(),b[i]-d)-v2.begin()]=b[i]-d;
        }
    }
    for(int i=1;i<=n;i++)
    {
        mx=max(mx,dp1[i]+dp2[i]-1);
    }
    printf("%d\n",mx);
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:7:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |     scanf("%d%d",&n,&d);
      |     ~~~~~^~~~~~~~~~~~~~
glo.cpp:10:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~

• 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