Submission #128459

#	Time	Username	Problem	Language	Result	Execution time	Memory
128459		letrongdat	Marriage questions (IZhO14_marriage)	C++17	40 / 100	1586 ms	2348 KiB

marriage

#include <bits/stdc++.h>
using namespace std;
#define forn(i, a, b)           for(int i=a; i<=b; ++i)
const int maxN = 3e4 +10;
const int maxM = 2e3 +10;
int matched[maxN];
vector<int> E[maxM];
int le, ri, t = 1;
int N, M, K;
long long result;
int visited[maxM];
vector<int> not_match;
bool visit(int u) {
    if (visited[u] == t) return false;
    visited[u] = t;
    while (E[u].back() < le) E[u].pop_back();
    for(auto v: E[u]) if (le <= v && v <= ri) {
        if (!matched[v] || visit(matched[v])) {
            matched[v] = u;
            return true;
        } 
    }
    return false;
}
int main() {
    ios::sync_with_stdio(0);
    cin >> N >> M >> K;
    forn(i, 1, K) {
        int Ai, Bi; 
        cin >> Ai >> Bi;
        E[Bi].push_back(Ai);
    }
    forn(i, 1, M) {
        sort(E[i].begin(), E[i].end());
        reverse(E[i].begin(), E[i].end());
    }
    forn(i, 1, M) not_match.push_back(i);
    for(le = 1; le <= N; ++le) {
        if (le > 1 && matched[le-1]) {
            not_match.push_back(matched[le-1]);
            matched[le-1] = 0;
        }
        while (ri < N && not_match.size()) {
            ri ++;
            t ++;
            while (not_match.size() && visit(not_match.back())) {
                t ++;
                not_match.pop_back();
            }
            
        }
        // cout << "check " << le << ' ' << ri << ' ' << matched[le] << '\n';
        // for(auto x: not_match) cout << x << ' ';
        // cout << '\n';
        // cout << "done\n";
        if (not_match.empty()) result += N-ri+1;
    }
    cout << result;
}

• Subtask 1: 40 / 100