oj.uz

Submission #804598

# Submission time Handle Problem Language Result Execution time Memory
804598 2023-08-03T10:06:00 Z taylor19 Exam (eJOI20_exam) C++14
12 / 100
 22 ms 4276 KB 
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

static inline int find_task(const vector<int> &A, const vector<int> &B)
{
    int n = (int)A.size();

    int target = B[0];
    bool t_2 = 1;
    for (int i = 1; i < n && t_2; ++i)
        if (B[i] == target)
            continue;
        else
            t_2 = 0;

    if (t_2)
        return 2;

    if (n <= (int)5e3)
        return 6;

    return 4;
}

static inline void task_2(vector<int> &A, const vector<int> &B)
{
    int n = (int)A.size();

    vector<int> next_to_left = {}, next_to_right = {};

    for (int i = 0; i < n; ++i)
        next_to_left.push_back(-1), next_to_right.push_back(n);

    stack<int> S;

    for (int i = 0; i < n; ++i)
    {
        while (!S.empty() && A[i] >= A[S.top()])
            next_to_right[S.top()] = i, S.pop();

        S.push(i);
    }

    while (!S.empty())
        S.pop();

    for (int i = (n - 1); i >= 0; --i)
    {
        while (!S.empty() && A[i] >= A[S.top()])
            next_to_left[S.top()] = i, S.pop();

        S.push(i);
    }

    vector<bool> Sel = {};
    for (int i = 0; i < n; ++i)
        Sel.push_back(0);

    for (int i = 0; i < n; ++i)
        if (A[i] == B[0] && !Sel[i])
        {
            int left = (next_to_left[i] + 1), right = (next_to_right[i] - 1);

            for (int j = left; j <= right; ++j)
                A[j] = B[0], Sel[j] = 1;
        }

    int ans = 0;

    for (int i = 0; i < n; ++i)
        if (A[i] == B[0])
            ++ans;

    cout << ans << '\n';

    return;
}

int main()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 0;
    cin >> n;

    vector<int> A = {}, B = {};

    for (int i = 1; i <= n; ++i)
    {
        int x = 0;
        cin >> x;

        A.push_back(x);
    }

    for (int i = 1; i <= n; ++i)
    {
        int y = 0;
        cin >> y;

        B.push_back(y);
    }

    int t = find_task(A, B);

    if (t == 2)
    {
        task_2(A, B);
        return 0;
    }

    return 0;
}

Subtask #1
0 / 14.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 5 ms 1236 KB Output is correct
3 Correct 13 ms 3264 KB Output is correct
4 Correct 10 ms 2648 KB Output is correct
5 Correct 22 ms 4276 KB Output is correct
6 Correct 12 ms 2748 KB Output is correct
7 Correct 14 ms 2840 KB Output is correct
8 Correct 19 ms 4260 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 16.0

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

Subtask #6
0 / 22.0

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