oj.uz

Submission #464937

# Submission time Handle Problem Language Result Execution time Memory
464937 2021-08-14T13:57:53 Z SamAnd Exam (eJOI20_exam) C++17
78 / 100
 1000 ms 175660 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 = 25000007;

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 ul[N], ur[N];
void pre()
{
    stack<int> s;
    for (int i = 1; i <= n; ++i)
    {
        while (!s.empty() && a[s.top()] <= a[i])
            s.pop();
        if (s.empty())
            ul[i] = 0;
        else
            ul[i] = s.top();
        s.push(i);
    }
    while (!s.empty())
        s.pop();
    for (int i = n; i >= 1; --i)
    {
        while (!s.empty() && a[s.top()] <= a[i])
            s.pop();
        if (s.empty())
            ur[i] = n + 1;
        else
            ur[i] = s.top();
        s.push(i);
    }
}

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 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;
}

map<int, int> mp;

int maxu[N * 4];
void ubd(int tl, int tr, int x, int y, int pos)
{
    if (tl == tr)
    {
        maxu[pos] = y;
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(tl, m, x, y, pos * 2);
    else
        ubd(m + 1, tr, x, y, pos * 2 + 1);
    maxu[pos] = max(maxu[pos * 2], maxu[pos * 2 + 1]);
}

int qry(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return 0;
    if (tl == l && tr == r)
        return maxu[pos];
    int m = (tl + tr) / 2;
    return max(qry(tl, m, l, min(m, r), pos * 2),
               qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}

int solv4()
{
    for (int i = 1; i <= n; ++i)
        mp[a[i]] = i;

    for (int i = 1; i <= n; ++i)
    {
        if (mp.find(b[i]) == mp.end())
            continue;
        int x = mp[b[i]];
        if (ul[x] < i && i < ur[x])
        {
            ubd(1, n, x, qry(1, n, 1, x, 1) + 1, 1);
        }
    }
    return maxu[1];
}

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

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

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

    pre();

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

    cout << solv4() << "\n";
}

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:157:18: warning: variable 'z' set but not used [-Wunused-but-set-variable]
  157 |             bool z = false;
      |                  ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 100548 KB Output is correct
2 Correct 44 ms 100568 KB Output is correct
3 Correct 45 ms 100576 KB Output is correct
4 Correct 44 ms 100508 KB Output is correct
5 Correct 45 ms 100504 KB Output is correct
6 Correct 43 ms 100548 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 7 ms 3020 KB Output is correct
3 Correct 20 ms 4428 KB Output is correct
4 Correct 17 ms 4544 KB Output is correct
5 Correct 30 ms 4552 KB Output is correct
6 Correct 19 ms 4612 KB Output is correct
7 Correct 18 ms 4600 KB Output is correct
8 Correct 31 ms 4676 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 100552 KB Output is correct
2 Correct 48 ms 103116 KB Output is correct
3 Correct 95 ms 116804 KB Output is correct
4 Correct 681 ms 164552 KB Output is correct
5 Correct 514 ms 168520 KB Output is correct
6 Correct 507 ms 168644 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3020 KB Output is correct
2 Correct 38 ms 6068 KB Output is correct
3 Correct 101 ms 10300 KB Output is correct
4 Correct 105 ms 11108 KB Output is correct
5 Correct 136 ms 11804 KB Output is correct
6 Correct 129 ms 11076 KB Output is correct
7 Correct 117 ms 11840 KB Output is correct
8 Correct 107 ms 10724 KB Output is correct
9 Correct 117 ms 11048 KB Output is correct
10 Correct 96 ms 11024 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 100548 KB Output is correct
2 Correct 44 ms 100568 KB Output is correct
3 Correct 45 ms 100576 KB Output is correct
4 Correct 44 ms 100508 KB Output is correct
5 Correct 45 ms 100504 KB Output is correct
6 Correct 43 ms 100548 KB Output is correct
7 Correct 45 ms 100488 KB Output is correct
8 Correct 43 ms 100640 KB Output is correct
9 Correct 46 ms 100900 KB Output is correct
10 Correct 45 ms 101396 KB Output is correct
11 Correct 44 ms 101360 KB Output is correct
12 Correct 43 ms 101328 KB Output is correct
13 Correct 47 ms 101380 KB Output is correct
14 Correct 45 ms 101376 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 100548 KB Output is correct
2 Correct 44 ms 100568 KB Output is correct
3 Correct 45 ms 100576 KB Output is correct
4 Correct 44 ms 100508 KB Output is correct
5 Correct 45 ms 100504 KB Output is correct
6 Correct 43 ms 100548 KB Output is correct
7 Correct 47 ms 100552 KB Output is correct
8 Correct 48 ms 103116 KB Output is correct
9 Correct 95 ms 116804 KB Output is correct
10 Correct 681 ms 164552 KB Output is correct
11 Correct 514 ms 168520 KB Output is correct
12 Correct 507 ms 168644 KB Output is correct
13 Correct 45 ms 100488 KB Output is correct
14 Correct 43 ms 100640 KB Output is correct
15 Correct 46 ms 100900 KB Output is correct
16 Correct 45 ms 101396 KB Output is correct
17 Correct 44 ms 101360 KB Output is correct
18 Correct 43 ms 101328 KB Output is correct
19 Correct 47 ms 101380 KB Output is correct
20 Correct 45 ms 101376 KB Output is correct
21 Correct 44 ms 101408 KB Output is correct
22 Correct 49 ms 106576 KB Output is correct
23 Correct 3 ms 2892 KB Output is correct
24 Execution timed out 1098 ms 175660 KB Time limit exceeded
25 Halted 0 ms 0 KB -