oj.uz

Submission #465570

# Submission time Handle Problem Language Result Execution time Memory
465570 2021-08-16T11:30:31 Z Sench2006 Exam (eJOI20_exam) C++14
53 / 100
 273 ms 199108 KB 
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;

#define ll long long
#define ar array

#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

// --------------- SOLUTION --------------- //

const int N = 1e5+5;
int n;
int a[N], b[N];
int nm[N], pm[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())
            pm[i] = 0;
        else
            pm[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())
            nm[i] = n + 1;
        else
            nm[i] = s.top();
        s.push(i);
    }
}

int t[N * 4];
void ubd(int tl, int tr, int x, int y, int pos)
{
    if (tl == tr)
    {
        t[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);
    t[pos] = max(t[pos * 2], t[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 t[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));
}
 
map <int, int> mp;
int segTreeSolve() {
    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 (pm[x] < i && i < nm[x]) {
            ubd(1, n, x, qry(1, n, 1, x, 1) + 1, 1);
        }
    }
    return t[1];
}

int dp[5001][5001];
int less5000() {
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (a[i] == b[j] && pm[i] < j && j < nm[i]) {
                dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + 1);
            }
            dp[i][j + 1] = max(dp[i][j + 1], dp[i][j]);
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
        }
    }
    for (int i = 1; i <= n + 1; ++i)
        for (int j = 1; j <= n + 1; ++j)
            ans = max(ans, dp[i][j]);
    return ans;
}

// int p[N];
// int sameBs() {
//     for (int i = 1; i <= n; ++i) {
//         p[i] = p[i - 1];
//         if (a[i] == b[i])
//             ++p[i];
//     }
 
//     next_max[0] = 0;
//     for (int i = 1; i <= n; ++i) {
//         if (a[i] > b[i]) {
//             next_max[i] = i;
//         }
//         else {
//             next_max[i] = next_max[i - 1];
//         }
//     }
//     prev_max[n + 1] = n + 1;
//     for (int i = n; i >= 1; --i) {
//         if (a[i] > b[i]) {
//             prev_max[i] = i;
//         }
//         else {
//             prev_max[i] = prev_max[i + 1];
//         }
//     }
 
//     int ans = 0;
//     for (int i = 1; i <= n; ++i) {
//         if (a[i] <= b[i] && p[prev_max[i] - 1] - p[next_max[i]] > 0) {
//                 ++ans;
//         }
//     }
 
//     return ans;
// }

void solve() { 
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        cin >> b[i];
 
    // bool ok = true;
    // for (int i = 1; i <= n; ++i)
    //     if (b[i] != b[1]) {
    //         ok = false;
    //         break;
    //     }
 
    // if (ok) {
    //     cout << sameBs() << "\n";
    //     return;
    // }
    pre();
    if (n <= 5000) {
        cout << less5000() << "\n";
        return;
    }
    cout << segTreeSolve() << "\n";
}

int main() {
    fastio;
    // fileio;
    int tests = 1;
    // cin >> tests;
    while (tests--) {
        solve();
    }

    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 1 ms 332 KB Output is correct
3 Correct 0 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 0 ms 332 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8196 KB Output is correct
2 Correct 11 ms 568 KB Output is correct
3 Correct 59 ms 5952 KB Output is correct
4 Incorrect 20 ms 1812 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 4 ms 3276 KB Output is correct
3 Correct 35 ms 23968 KB Output is correct
4 Correct 170 ms 94332 KB Output is correct
5 Runtime error 273 ms 199108 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 588 KB Output is correct
2 Correct 36 ms 3012 KB Output is correct
3 Correct 100 ms 6724 KB Output is correct
4 Correct 105 ms 6848 KB Output is correct
5 Correct 128 ms 7544 KB Output is correct
6 Correct 145 ms 7720 KB Output is correct
7 Correct 106 ms 7592 KB Output is correct
8 Correct 102 ms 7108 KB Output is correct
9 Correct 120 ms 7576 KB Output is correct
10 Correct 93 ms 7764 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 1 ms 332 KB Output is correct
3 Correct 0 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 0 ms 332 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 716 KB Output is correct
10 Correct 1 ms 1228 KB Output is correct
11 Correct 1 ms 1228 KB Output is correct
12 Correct 1 ms 1224 KB Output is correct
13 Correct 1 ms 1228 KB Output is correct
14 Correct 1 ms 1228 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 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 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 4 ms 3276 KB Output is correct
9 Correct 35 ms 23968 KB Output is correct
10 Correct 170 ms 94332 KB Output is correct
11 Runtime error 273 ms 199108 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -