Submission #804598

#	Time	Username	Problem	Language	Result	Execution time	Memory
804598		taylor19	Exam (eJOI20_exam)	C++14	12 / 100	22 ms	4276 KiB

exam

#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
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22