Submission #1096978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096978		ivaziva	Rabbit Carrot (LMIO19_triusis)	C++14	0 / 100	1 ms	344 KiB

triusis

#include <bits/stdc++.h>

using namespace std;

#define MAXN 200001

int n,m;
int a[MAXN];
vector<int> kompresija;
int seg[MAXN*4];

void update(int node,int l,int r,int pos,int val)
{
    if (l==r) seg[node]=max(seg[node],val);
    else
    {
        int mid=(l+r)/2;
        if (pos<=mid) update(2*node,l,mid,pos,val);
        else update(2*node+1,mid+1,r,pos,val);
        seg[node]=max(seg[2*node],seg[2*node+1]);
    }
}

int query(int node,int l,int r,int aa,int bb)
{
    if (aa>bb) return -INT_MAX;
    if (l==aa and r==bb) return seg[node];
    int mid=(l+r)/2;
    return max(query(2*node,l,mid,aa,min(bb,mid)),query(2*node+1,mid+1,r,max(aa,mid+1),bb));
}

int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=n;i++) a[i]+=m*(n-i);
    for (int i=1;i<=n;i++) kompresija.push_back(a[i]);
    sort(kompresija.begin(),kompresija.end());
    kompresija.erase(unique(kompresija.begin(),kompresija.end()),kompresija.end());
    for (int i=1;i<=n;i++) a[i]=lower_bound(kompresija.begin(),kompresija.end(),a[i])-kompresija.begin();
    int ans=0;
    for (int i=1;i<=n;i++)
    {
        int sol=query(1,0,kompresija.size()-1,a[i],kompresija.size()-1);
        ans=max(ans,sol+1);
        update(1,0,kompresija.size()-1,a[i],sol+1);
    }
    cout<<ans<<endl;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37