oj.uz

Submission #875918

# Submission time Handle Problem Language Result Execution time Memory
875918 2023-11-20T18:18:00 Z maxFedorchuk Exam (eJOI20_exam) C++14
100 / 100
 364 ms 211232 KB 
#include <bits/stdc++.h>
using namespace std;

const long long MXN=1e5+10;
const long long MX=5050;
const long long INF=1e18;
const long long lg=20;

long long sc[MXN],nd[MXN];
long long spars[lg][MXN];
long long dp[MX][MX];
long long mas[MXN];

long long n;

void cntspr()
{
    for(long long i=1;i<=n;i++)
    {
        spars[0][i]=sc[i];
    }

    for(long long i=1;i<lg;i++)
    {
        long long zd=(1LL<<i);
        long long pzd=zd/2;

        for(long long j=1;j<=(n-zd+1);j++)
        {
            spars[i][j]=max(spars[i-1][j],spars[i-1][j+pzd]);
        }
    }

    return;
}

long long zap(long long l,long long r)
{
    long long sl=log2(r-l+1);
    long long zd=(1LL<<sl);

    return max(spars[sl][l],spars[sl][r-zd+1]);
}

void fun1()
{
    for(long long i=1;i<=n;i++)
    {
        for(long long j=1;j<=n;j++)
        {
            if(sc[i]==nd[j] && zap(min(i,j),max(i,j))==nd[j])
            {
                dp[i][j]=dp[i][j-1]+1;
            }
            else
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }

    cout<<dp[n][n]<<"\n";

    return;
}

void fun2()
{
    map < long long , long long > mp;
    for(long long i=1;i<=n;i++)
    {
        mp[sc[i]]=i;
    }

    vector < long long > psl;

    for(long long i=1;i<=n;i++)
    {
        if(mp.find(nd[i])!=mp.end())
        {
            if(zap(min(mp[nd[i]],i),max(mp[nd[i]],i))==nd[i])
            {
                psl.push_back(mp[nd[i]]);
            }
        }
    }

    mas[0]=0;
    for(long long i=1;i<=n+2;i++)
    {
        mas[i]=INF;
    }

    long long res=0;
    for(auto u:psl)
    {
        long long l=0,r=n+2;

        while((l+1)<r)
        {
            long long mid=(l+r)/2;

            if(mas[mid]<=u)
            {
                l=mid;
            }
            else
            {
                r=mid;
            }
        }

        mas[r]=u;
        res=max(res,r);
    }

    cout<<res<<"\n";
    return;
}

void fun3()
{
    for(long long i=1;i<=n;i++)
    {
        if(sc[i]==nd[i])
        {
            if(sc[i-1]!=nd[i-1])
            {
                for(long long j=i-1;(j>=1 && sc[j]<nd[j]);j--)
                {
                    sc[j]=nd[j];
                }
            }

            if(sc[i+1]!=nd[i+1])
            {
                for(long long j=i+1;(j<=n && sc[j]<nd[j]);j++)
                {
                    sc[j]=nd[j];
                }
            }
        }
    }

    long long res=0;

    for(long long i=1;i<=n;i++)
    {
        res+=(sc[i]==nd[i]);
    }

    cout<<res<<"\n";
    return;
}
int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin>>n;

    for(long long i=1;i<=n;i++)
    {
        cin>>sc[i];
    }

    for(long long i=1;i<=n;i++)
    {
        cin>>nd[i];
    }

    cntspr();

    if(n<=5000)
    {
        fun1();
        return 0;
    }

    for(int i=1;i<=n;i++)
    {
        if(nd[i]!=nd[1])
        {
            fun2();
            return 0;
        }
    }

    fun3();
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 28248 KB Output is correct
2 Correct 5 ms 13232 KB Output is correct
3 Correct 13 ms 17240 KB Output is correct
4 Correct 12 ms 16732 KB Output is correct
5 Correct 19 ms 18260 KB Output is correct
6 Correct 13 ms 16568 KB Output is correct
7 Correct 14 ms 16728 KB Output is correct
8 Correct 18 ms 18268 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 3 ms 14188 KB Output is correct
3 Correct 17 ms 66804 KB Output is correct
4 Correct 53 ms 202880 KB Output is correct
5 Correct 52 ms 211024 KB Output is correct
6 Correct 50 ms 211188 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 13148 KB Output is correct
2 Correct 29 ms 20712 KB Output is correct
3 Correct 77 ms 25772 KB Output is correct
4 Correct 84 ms 26604 KB Output is correct
5 Correct 92 ms 27524 KB Output is correct
6 Correct 86 ms 26788 KB Output is correct
7 Correct 88 ms 27180 KB Output is correct
8 Correct 77 ms 25852 KB Output is correct
9 Correct 84 ms 26380 KB Output is correct
10 Correct 61 ms 26520 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 1 ms 7004 KB Output is correct
10 Correct 2 ms 9564 KB Output is correct
11 Correct 1 ms 9564 KB Output is correct
12 Correct 2 ms 9564 KB Output is correct
13 Correct 2 ms 9564 KB Output is correct
14 Correct 2 ms 9564 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 3 ms 14188 KB Output is correct
9 Correct 17 ms 66804 KB Output is correct
10 Correct 53 ms 202880 KB Output is correct
11 Correct 52 ms 211024 KB Output is correct
12 Correct 50 ms 211188 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 1 ms 7004 KB Output is correct
16 Correct 2 ms 9564 KB Output is correct
17 Correct 1 ms 9564 KB Output is correct
18 Correct 2 ms 9564 KB Output is correct
19 Correct 2 ms 9564 KB Output is correct
20 Correct 2 ms 9564 KB Output is correct
21 Correct 1 ms 9560 KB Output is correct
22 Correct 9 ms 28252 KB Output is correct
23 Correct 364 ms 211144 KB Output is correct
24 Correct 170 ms 211228 KB Output is correct
25 Correct 76 ms 211024 KB Output is correct
26 Correct 52 ms 211232 KB Output is correct
27 Correct 70 ms 211192 KB Output is correct
28 Correct 50 ms 211208 KB Output is correct
29 Correct 50 ms 211184 KB Output is correct
30 Correct 52 ms 211028 KB Output is correct
31 Correct 48 ms 211028 KB Output is correct
32 Correct 49 ms 211024 KB Output is correct