oj.uz

Submission #1096978

# Submission time Handle Problem Language Result Execution time Memory
1096978 2024-10-05T15:33:56 Z ivaziva Rabbit Carrot (LMIO19_triusis) C++14
0 / 100
 1 ms 344 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -