Submission #1311723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311723		andreidumitrache	Exam (eJOI20_exam)	C++20	14 / 100	4 ms	1344 KiB

exam

#include <bits/stdc++.h>
using namespace std;

struct Interval {
    int l, r;
};

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

    int N;
    cin >> N;
    vector<long long> A(N), B(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) cin >> B[i];

    // 1️⃣ Calculăm L[j] și R[j] folosind monotonic stack
    vector<int> L(N), R(N);
    stack<int> st;

    // L[j]: primul element la stânga mai mare decât A[j]
    for (int i = 0; i < N; i++) {
        while (!st.empty() && A[st.top()] <= A[i]) st.pop();
        L[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }

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

    // R[j]: primul element la dreapta mai mare decât A[j]
    for (int i = N-1; i >= 0; i--) {
        while (!st.empty() && A[st.top()] <= A[i]) st.pop();
        R[i] = st.empty() ? N : st.top();
        st.push(i);
    }

    // 2️⃣ Grupăm intervalele și pozițiile după valoare
    map<long long, vector<Interval>> intervals;
    map<long long, vector<int>> positions;

    for (int i = 0; i < N; i++) {
        intervals[A[i]].push_back({L[i]+1, R[i]-1});
        positions[B[i]].push_back(i);
    }

    int result = 0;

    // 3️⃣ Greedy pentru fiecare valoare
    for (auto &p : positions) {
        long long val = p.first;
        vector<int> &pos = p.second;
        vector<Interval> &ints = intervals[val];

        if (ints.empty()) continue;

        // sortam intervalele după stânga
        sort(ints.begin(), ints.end(), [](const Interval &a, const Interval &b){
            return a.l < b.l;
        });

        // sortam pozițiile
        sort(pos.begin(), pos.end());

        // priority queue pentru a selecta intervalul cu R minim
        priority_queue<int, vector<int>, greater<int>> pq;
        int idx = 0;

        for (int x : pos) {
            // adaugăm intervalele care încep înainte sau la x
            while (idx < (int)ints.size() && ints[idx].l <= x) {
                pq.push(ints[idx].r);
                idx++;
            }

            // scoatem intervalele care nu mai pot acoperi x
            while (!pq.empty() && pq.top() < x) pq.pop();

            if (!pq.empty()) {
                result++;
                pq.pop(); // folosim intervalul
            }
        }
    }

    cout << result << "\n";
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22