Submission #1220138

#TimeUsernameProblemLanguageResultExecution timeMemory
1220138Theo830Marriage questions (IZhO14_marriage)C++20
38 / 100
1595 ms16488 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e9+7; const ll MOD = 998244353; typedef pair<ll,ll> ii; #define iii pair<ll,ii> #define id pair<ll,vector<ll> > #define f(i,a,b) for(ll i = a;i < b;i++) #define pb push_back #define vll vector<ll> #define F first #define S second #define all(x) (x).begin(), (x).end() ///I hope I will get uprating and don't make mistakes ///I will never stop programming ///sqrt(-1) Love C++ ///Please don't hack me ///@TheofanisOrfanou Theo830 ///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst) ///Stay Calm ///Look for special cases ///Beware of overflow and array bounds ///Think the problem backwards ///Training ll n,m,k; vector<set<ll> >adj,rev; bool ok(ll l,ll r){ vector<set<ll> >X = rev; ll posa[n+5] = {0}; set<ii>ex; f(i,1,m+1){ set<ll>fkale; for(auto x:X[i]){ if(x < l || x > r){ fkale.insert(x); } else{ posa[x]++; } } for(auto x:fkale){ X[i].erase(x); } ex.insert(ii(X[i].size(),i)); } while(!ex.empty()){ ii f = (*ex.begin()); ex.erase(f); if(f.F == 0){ return false; } ll go = -1; ll d = INF; for(auto x:X[f.S]){ if(d > posa[x]){ go = x; } } for(auto x:X[f.S]){ posa[x]--; } for(auto x:adj[go]){ if(ex.count(ii(X[x].size(),x))){ ex.erase(ii(X[x].size(),x)); X[x].erase(go); ex.insert(ii(X[x].size(),x)); } } } return true; } int main(void){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>m>>k; adj.assign(n+5,set<ll>()); rev.assign(m+5,set<ll>()); f(i,0,k){ ll a,b; cin>>a>>b; adj[a].insert(b); rev[b].insert(a); } ll ans = 0; f(i,0,n){ ll l = i,r = n-1; ll posa = n; while(l <= r){ ll mid = (l+r)/2; if(ok(i+1,mid+1)){ r = mid - 1; posa = min(posa,mid); } else{ l = mid + 1; } } ans += n - posa; } cout<<ans<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...