oj.uz

Submission #462193

# Submission time Handle Problem Language Result Execution time Memory
462193 2021-08-10T08:36:41 Z Tenis0206 Exam (eJOI20_exam) C++11
100 / 100
 133 ms 15388 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++)
    {
        vector<pair<int,int>> upd;
        for(int j=1;j<=n;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);
            upd.push_back({j,dp2[i][j]});
            Max = max(Max,dp2[i][j]);
        }
        for(auto it : upd)
        {
            aib.update(it.first,it.second);
        }
    }
    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 1 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 1 ms 320 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 320 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 1100 KB Output is correct
3 Correct 20 ms 3496 KB Output is correct
4 Correct 17 ms 2956 KB Output is correct
5 Correct 32 ms 4228 KB Output is correct
6 Correct 19 ms 2776 KB Output is correct
7 Correct 20 ms 2764 KB Output is correct
8 Correct 30 ms 4108 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 716 KB Output is correct
5 Correct 4 ms 772 KB Output is correct
6 Correct 5 ms 844 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 816 KB Output is correct
2 Correct 47 ms 3964 KB Output is correct
3 Correct 124 ms 8328 KB Output is correct
4 Correct 132 ms 9124 KB Output is correct
5 Correct 128 ms 9592 KB Output is correct
6 Correct 131 ms 8900 KB Output is correct
7 Correct 124 ms 9676 KB Output is correct
8 Correct 108 ms 8744 KB Output is correct
9 Correct 133 ms 8880 KB Output is correct
10 Correct 88 ms 8812 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 320 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 320 KB Output is correct
7 Correct 1 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 576 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 1 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 1 ms 320 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 320 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 716 KB Output is correct
11 Correct 4 ms 772 KB Output is correct
12 Correct 5 ms 844 KB Output is correct
13 Correct 1 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 576 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 117 ms 13472 KB Output is correct
25 Correct 51 ms 5560 KB Output is correct
26 Correct 29 ms 1668 KB Output is correct
27 Correct 42 ms 11212 KB Output is correct
28 Correct 27 ms 588 KB Output is correct
29 Correct 32 ms 13368 KB Output is correct
30 Correct 31 ms 13724 KB Output is correct
31 Correct 32 ms 15388 KB Output is correct
32 Correct 33 ms 8388 KB Output is correct