oj.uz

Submission #464569

# Submission time Handle Problem Language Result Execution time Memory
464569 2021-08-13T12:48:08 Z SamAnd Exam (eJOI20_exam) C++17
42 / 100
 641 ms 148804 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 100005, N0 = 5003;
int M = 20000007;

bool isprime(int x)
{
    if (x <= 1)
        return false;
    for (int i = 2; i * i <= x; ++i)
    {
        if (x % i == 0)
            return false;
    }
    return true;
}

int n;
int a[N], b[N];

int maxi[N0][N0];

vector<int> v[N];

void rec0(int l, int r, int p)
{
    if (l > r)
        return;
    int m = maxi[l][r];
    rec0(l, m - 1, m);
    rec0(m + 1, r, m);

    if (p == 0)
        return;
    else if (p == l - 1)
    {
        for (int i = l; i <= r; ++i)
        {
            if (b[i] == a[p])
                v[m].push_back(i);
        }
    }
    else if (p == r + 1)
    {
        for (int i = r; i >= l; --i)
        {
            if (b[i] == a[p])
                v[m].push_back(i);
        }
        reverse(all(v[m]));
    }
    else
        assert(false);
}

int* dp;
int rec(int l, int r, int ul, int ur, int p)
{
    if (l > r)
        return 0;
    ul = max(ul, l - 1);
    ur = min(ur, r + 1);
    if (ul + 1 >= ur)
        return 0;

    int m = maxi[l][r];

    ll h = (ul * 1LL * N0 * N0 + m * 1LL * N0 + ur) % M;

    if (dp[h] != -1)
        return dp[h];

    if (ul < m && m < ur && a[m] == b[m])
        dp[h] = rec(l, m - 1, ul, ur, m) + rec(m + 1, r, ul, ur, m) + 1;
    else
        dp[h] = rec(l, m - 1, ul, ur, m) + rec(m + 1, r, ul, ur, m);

    if (p == 0)
    {
        return dp[h];
    }

    if (p == l - 1)
    {
        int q = 0;
        //for (int i = ul + 1; i <= ur - 1; ++i)
        int s = upper_bound(all(v[m]), ul) - v[m].begin();
        for (int ii = s; ii < sz(v[m]); ++ii)
        {
            int i = v[m][ii];

            if (!(ul < i && i < ur))
                break;

            bool z = false;
            if (b[i] == a[p])
            {
                z = true;
                ++q;
            }
            if (i < m && m < ur && a[m] == b[m])
                ++q;
            if (z)
                dp[h] = max(dp[h], q + rec(l, m - 1, i, ur, m) + rec(m + 1, r, i, ur, m));
            if (i < m && m < ur && a[m] == b[m])
                --q;
        }
    }
    else if (p == r + 1)
    {
        int q = 0;
        //for (int i = ur - 1; i >= ul + 1; --i)
        int s = lower_bound(all(v[m]), ur) - v[m].begin();
        for (int ii = s - 1; ii >= 0; --ii)
        {
            int i = v[m][ii];

            if (!(ul < i && i < ur))
                continue;

            bool z = false;
            if (b[i] == a[p])
            {
                z = true;
                ++q;
            }
            if (ul < m && m < i && a[m] == b[m])
                ++q;
            dp[h] = max(dp[h], q + rec(l, m - 1, ul, i, m) + rec(m + 1, r, ul, i, m));
            if (ul < m && m < i && a[m] == b[m])
                --q;
        }
    }
    else
        assert(false);

    return dp[h];
}

int solv0()
{
    for (int l = 1; l <= n; ++l)
    {
        maxi[l][l] = l;
        for (int r = l + 1; r <= n; ++r)
        {
            maxi[l][r] = maxi[l][r - 1];
            if (a[r] > a[maxi[l][r]])
                maxi[l][r] = r;
        }
    }

    for (int i = 1; i <= n; ++i)
        v[i].clear();
    rec0(1, n, 0);

    dp = new int[M];
    for (int i = 0; i < M; ++i)
        dp[i] = -1;
    return rec(1, n, 0, n + 1, 0);
}

int p[N];
int ul[N], ur[N];
int solv2()
{
    for (int i = 1; i <= n; ++i)
    {
        p[i] = p[i - 1];
        if (a[i] == b[i])
            ++p[i];
    }

    ul[0] = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] > b[i])
        {
            ul[i] = i;
        }
        else
        {
            ul[i] = ul[i - 1];
        }
    }
    ur[n + 1] = n + 1;
    for (int i = n; i >= 1; --i)
    {
        if (a[i] > b[i])
        {
            ur[i] = i;
        }
        else
        {
            ur[i] = ur[i + 1];
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (a[i] <= b[i])
        {
            if (p[ur[i] - 1] - p[ul[i]] > 0)
                ++ans;
        }
    }

    return ans;
}

void solv()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        cin >> b[i];

    if (n <= 5000)
    {
        cout << solv0() << "\n";
        return;
    }

    bool z2 = true;
    for (int i = 1; i <= n; ++i)
    {
        if (b[i] != b[1])
        {
            z2 = false;
            break;
        }
    }

    if (z2)
    {
        cout << solv2() << "\n";
        return;
    }
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    while (!isprime(M))
        ++M;

    /*int st = 100;
    while (st--)
    {
        n = rnf() % 100 + 1;
        for (int i = 1; i <= n; ++i)
        {
            a[i] = rnf() % 100 + 1;
        }
        b[1] = a[rnf() % n + 1];
        for (int i = 2; i <= n; ++i)
            b[i] = b[1];

        if (solv0() != solv2())
        {
            cout << "WA\n";
            return 0;
        }
    }
    cout << "OK\n";
    return 0;*/

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

Compilation message

exam.cpp: In function 'int rec(int, int, int, int, int)':
exam.cpp:129:18: warning: variable 'z' set but not used [-Wunused-but-set-variable]
  129 |             bool z = false;
      |                  ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 80948 KB Output is correct
2 Correct 35 ms 80960 KB Output is correct
3 Correct 38 ms 80972 KB Output is correct
4 Correct 35 ms 80960 KB Output is correct
5 Correct 39 ms 80960 KB Output is correct
6 Correct 41 ms 80932 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 86900 KB Output is correct
2 Correct 7 ms 3020 KB Output is correct
3 Correct 20 ms 4392 KB Output is correct
4 Correct 18 ms 4532 KB Output is correct
5 Correct 31 ms 4600 KB Output is correct
6 Correct 19 ms 4584 KB Output is correct
7 Correct 19 ms 4584 KB Output is correct
8 Correct 29 ms 4556 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 80992 KB Output is correct
2 Correct 39 ms 83464 KB Output is correct
3 Correct 92 ms 97124 KB Output is correct
4 Correct 641 ms 144860 KB Output is correct
5 Incorrect 478 ms 148804 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 80948 KB Output is correct
2 Correct 35 ms 80960 KB Output is correct
3 Correct 38 ms 80972 KB Output is correct
4 Correct 35 ms 80960 KB Output is correct
5 Correct 39 ms 80960 KB Output is correct
6 Correct 41 ms 80932 KB Output is correct
7 Correct 35 ms 80916 KB Output is correct
8 Correct 35 ms 81120 KB Output is correct
9 Correct 36 ms 81320 KB Output is correct
10 Correct 36 ms 81892 KB Output is correct
11 Correct 36 ms 81868 KB Output is correct
12 Correct 37 ms 81776 KB Output is correct
13 Correct 36 ms 81760 KB Output is correct
14 Correct 38 ms 81884 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 80948 KB Output is correct
2 Correct 35 ms 80960 KB Output is correct
3 Correct 38 ms 80972 KB Output is correct
4 Correct 35 ms 80960 KB Output is correct
5 Correct 39 ms 80960 KB Output is correct
6 Correct 41 ms 80932 KB Output is correct
7 Correct 37 ms 80992 KB Output is correct
8 Correct 39 ms 83464 KB Output is correct
9 Correct 92 ms 97124 KB Output is correct
10 Correct 641 ms 144860 KB Output is correct
11 Incorrect 478 ms 148804 KB Output isn't correct
12 Halted 0 ms 0 KB -