oj.uz

Submission #462194

# Submission time Handle Problem Language Result Execution time Memory
462194 2021-08-10T08:37:52 Z Tenis0206 Exam (eJOI20_exam) C++11
100 / 100
 152 ms 15236 KB 
#include <bits/stdc++.h>

using namespace std;
int n;
int a[100005],b[100005],aux[100005],l[100005],r[100005],fr[100005];
int dp[100005],dp2[5005][5005];
class arbore_indexat_binar
{
    int aib[100005];
private:
    int ub(int x)
    {
        return (x&(-x));
    }
public:
    void update(int poz, int val)
    {
        for(int i=poz;i<=n;i+=ub(i))
        {
            aib[i] = max(aib[i],val);
        }
    }
    int query(int poz)
    {
        int rez = 0;
        for(int i=poz;i>=1;i-=ub(i))
        {
            rez = max(rez,aib[i]);
        }
        return rez;
    }
} aib;
bool subtask2()
{
    for(int i=2; i<=n; i++)
    {
        if(b[i]!=b[i-1])
        {
            return false;
        }
    }
    return true;
}
bool subtask4()
{
    for(int i=1; i<=n; i++)
    {
        aux[i] = a[i];
    }
    sort(aux+1,aux+n+1);
    for(int i=2; i<=n; i++)
    {
        if(aux[i]==aux[i-1])
        {
            return false;
        }
    }
    return true;
}
void precalc_stack()
{
    stack<int> st;
    for(int i=1; i<=n; i++)
    {
        while(!st.empty() && a[i]>a[st.top()])
        {
            st.pop();
        }
        if(st.empty())
        {
            l[i] = 0;
        }
        else
        {
            l[i] = st.top();
        }
        st.push(i);
    }
    while(!st.empty())
    {
        st.pop();
    }
    for(int i=n; i>=1; i--)
    {
        while(!st.empty() && a[i]>a[st.top()])
        {
            st.pop();
        }
        if(st.empty())
        {
            r[i] = n+1;
        }
        else
        {
            r[i] = st.top();
        }
        st.push(i);
    }
}
int solve_subtask2()
{
    for(int i=1; i<=n; i++)
    {
        if(a[i]==b[1])
        {
            ++fr[l[i]+1];
            --fr[r[i]];
        }
    }
    int rez = 0;
    for(int i=1; i<=n; i++)
    {
        fr[i]+=fr[i-1];
        if(fr[i])
        {
            ++rez;
        }
    }
    return rez;
}
int solve_subtask4()
{
    map<int,int> poz;
    for(int i=1;i<=n;i++)
    {
        poz[a[i]] = i;
    }
    int Max = 0;
    for(int i=1;i<=n;i++)
    {
        if(poz[b[i]]>i && l[poz[b[i]]]>=i)
        {
            continue;
        }
        if(poz[b[i]]<i && r[poz[b[i]]]<=i)
        {
            continue;
        }
        dp[i] = 1 + aib.query(poz[b[i]]);
        aib.update(poz[b[i]],dp[i]);
        Max = max(Max,dp[i]);
    }
    return Max;
}
int solve_general()
{
    int Max = 0;
    for(int i=1;i<=n;i++)
    {
        for(int j=n;j>=1;j--)
        {
            if(a[j]!=b[i])
            {
                continue;
            }
            if(j>i && l[j]>=i)
            {
                continue;
            }
            if(j<i && r[j]<=i)
            {
                continue;
            }
            dp2[i][j] = 1 + aib.query(j);
            aib.update(j,dp2[i][j]);
            Max = max(Max,dp2[i][j]);
        }
    }
    return Max;
}
int main()
{
  //  freopen("nr.in","r",stdin);
  //  freopen("nr.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    for(int i=1; i<=n; i++)
    {
        cin>>b[i];
    }
    precalc_stack();
    if(subtask2())
    {
        cout<<solve_subtask2()<<'\n';
        return 0;
    }
    if(subtask4())
    {
        cout<<solve_subtask4()<<'\n';
        return 0;
    }
    cout<<solve_general()<<'\n';
    return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 6 ms 716 KB Output is correct
3 Correct 20 ms 2360 KB Output is correct
4 Correct 17 ms 2572 KB Output is correct
5 Correct 38 ms 2284 KB Output is correct
6 Correct 19 ms 2340 KB Output is correct
7 Correct 20 ms 2192 KB Output is correct
8 Correct 28 ms 2216 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 5 ms 708 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 7 ms 716 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 720 KB Output is correct
2 Correct 51 ms 3168 KB Output is correct
3 Correct 133 ms 7164 KB Output is correct
4 Correct 137 ms 7352 KB Output is correct
5 Correct 152 ms 7680 KB Output is correct
6 Correct 127 ms 7696 KB Output is correct
7 Correct 126 ms 7732 KB Output is correct
8 Correct 133 ms 7556 KB Output is correct
9 Correct 125 ms 7656 KB Output is correct
10 Correct 91 ms 7744 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 844 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 5 ms 708 KB Output is correct
11 Correct 4 ms 716 KB Output is correct
12 Correct 7 ms 716 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 588 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 844 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 126 ms 13356 KB Output is correct
25 Correct 46 ms 5520 KB Output is correct
26 Correct 28 ms 1656 KB Output is correct
27 Correct 49 ms 11204 KB Output is correct
28 Correct 26 ms 504 KB Output is correct
29 Correct 31 ms 13316 KB Output is correct
30 Correct 32 ms 13660 KB Output is correct
31 Correct 33 ms 15236 KB Output is correct
32 Correct 32 ms 8344 KB Output is correct