Submission #343779

#	Time	Username	Problem	Language	Result	Execution time	Memory
343779		apostoldaniel854	Marriage questions (IZhO14_marriage)	C++14	100 / 100	671 ms	2924 KiB

marriage

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
using ll = long long;

const int MAX_N = 3e4;
vector <int> gr[1 + MAX_N];
int pereche[1 + MAX_N];
int viz[1 + MAX_N];

int t;
int lb, rb;

bool bkt_op (int fata);

bool fits_req (int baiat) {
    return lb <= baiat && baiat <= rb && (not pereche[baiat] || bkt_op (pereche[baiat]));
}

bool bkt_op (int fata) {
    if (viz[fata] != t) {
        viz[fata] = t;
        for (int gagic : gr[fata]) {
            if (fits_req (gagic)) {
                pereche[gagic] = fata;
                return true;
            }
        }
    }
    return false;
}
int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++) {
        int x, y;
        cin >> x >> y;
        gr[y].pb (x);
    }
    for (int i = 1; i <= m; i++)
        sort (gr[i].begin (), gr[i].end ());
    lb = rb = 1;
    ll ans = 0;
    for (int i = 1; i <= m; i++) {
		t++;
		while(rb <= n && not bkt_op (i)) rb++, t++;
		if (rb > n) {
            cout << ans << "\n";
            return 0;
        }
    }
    vector <int> unpaired;
    while (lb <= n) {
        while (unpaired.size ()) {
            int cur = unpaired.back ();
            unpaired.pop_back ();
            t++;
            while(rb <= n && not bkt_op (cur)) rb++, t++;
            if (rb > n) {
                cout << ans << "\n";
                return 0;
            }
        }
        ans += (n - rb + 1);
        if (pereche[lb]) {
            unpaired.pb (pereche[lb]);
            pereche[lb] = 0;
        }
        lb++;
    }
    cout << ans << "\n";
    return 0;
}

• Subtask 1: 100 / 100