Submission #936139

#	Time	Username	Problem	Language	Result	Execution time	Memory
936139		vjudge1	Global Warming (CEOI18_glo)	C++17	10 / 100	31 ms	8300 KiB

glo

#include <bits/stdc++.h>
#define fi first
#define se second
#define FOR(i,l,r) for (int i = l; i <= r; i++)
#define FORD(i,l,r) for (int i = l; i >= r; i--)
#define el cout <<"\n"
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define MASK(i) ((1LL)<<(i))
#define BIT(x,i) (((x)>>(i))&(1LL))
using namespace std;

const long long N=1e6+5;
const long long base=311;
const long long mod=1e9+7;
const long long INF=1e9+7;
 int n,x;
 vector<int>a(N+1),f(N+1);
int LIS()
{
        f[1]=1;
    int ans=1;
    for (int i=2;i<=n;i++)
    {
        int l=1,r=ans,j=0;
        while (l<=r)
        {
            int mid=(l+r)/2;
            if (a[i]>a[f[mid]])
            {
                j=mid;
                l=mid+1;
            }
            else
            {
                r=mid-1;
            }
        }
        if (j==ans)
        {
            f[++ans]=i;
        }
        if (a[i]<a[f[j+1]])
        {
            f[j+1]=i;
        }
    }
    return ans;
}
void ip()
{
    cin>>n>>x;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    if(x==0)
    {
        cout<<LIS()<<endl;
    }
}
int main()
{
//    freopen("nhap.inp","r",stdin);
//    freopen("nhap.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--)
    {
        ip();
    }
    return 0;
}

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