제출 #1260583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260583		SzymonKrzywda	Arranging Tickets (JOI17_arranging_tickets)	C++20	0 / 100	2 ms	4928 KiB

arranging_tickets

#include <iostream>
#include <queue>

using namespace std;

int maxi = 0, maxi_pos = 0;

const int MAXN = 2e5 + 4;
vector<int> konce[MAXN];
int sumy[MAXN];

int n, m, a, b, c;

bool check(int maxi_val, int k) {
    priority_queue<int> kolejka;
    int ile_usunalem = 0;

    vector<int> sumy2(n + 2, 0);

    for (int i = 1; i <= maxi_pos; i++) {
        for (int k : konce[i]) kolejka.push(k);
        int wzorek = sumy[i] - maxi_val + (k - (sumy[i] + maxi_val) + 1) / 2;
        while (wzorek > ile_usunalem && kolejka.size()) {
            int koniec = kolejka.top();
            kolejka.pop();
            ile_usunalem++;
            sumy2[maxi_pos]--;
            sumy2[koniec + 1] ++;
        }

        if (wzorek > ile_usunalem) return 0;
    }

    for (int i = maxi_pos + 1; i <= n; i++) {
        sumy2[i] += sumy2[i - 1];
        if (sumy2[i] + sumy[i] > maxi_val) return 0;
    }


    return 1;
}


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

    cin >> n >> m;

    vector<pair<int, int>> prz;

    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        if (a > b) swap(a, b); 
        b--;
        prz.push_back({a, b});
        sumy[a]++;
        sumy[b + 1] --;
    }
    


    for (int i = 1; i <= n; i++) {
        sumy[i] += sumy[i - 1];
        if (maxi > sumy[i]) maxi_pos = i;
        maxi = max(sumy[i], maxi);
    }

    for (int i = 0; i < m; i++) {
        if (prz[i].first <= i && prz[i].second >= i) konce[prz[i].first].push_back(prz[i].second);
    }


    for (int i = 0; i <= n; i++) {
        sort(konce[i].begin(), konce[i].end());
    }

    int left = 0, right = maxi;
    while (left < right) {
        int mid = (left + right) / 2;
        if (check(mid, maxi - mid) || check(mid, maxi - mid + 1)) right = mid;
        else left = mid + 1;
    }
    
    cout << left << '\n';

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 35
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 15