fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define all(x) (x).begin(), (x).end()
  5. #define sz(x) (int)(x).size()
  6. using LL = long long;
  7.  
  8. template<class T, size_t D>
  9. struct vec : vector<vec<T, D - 1>> {
  10.     template<class... Args>
  11.     vec(int n = 0, Args... args) 
  12.         : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
  13. };
  14. template<class T>
  15. struct vec<T, 1> : vector<T> {
  16.     vec(int n = 0, T val = T()) 
  17.         : vector<T>(n, val) {}
  18. };
  19.  
  20. template<class T>
  21. inline bool asMn(T& a, const T& b) {return a > b ? a = b, true : false;}
  22. template<class T>
  23. inline bool asMx(T& a, const T& b) {return a < b ? a = b, true : false;}
  24.  
  25. inline int nxt(int i, int n) {return i == n - 1 ? 0 : i + 1;}
  26. inline int prv(int i, int n) {return !i ? n - 1 : i - 1;}
  27.  
  28. const int inf = 1e9;
  29. mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
  30.  
  31. template<class maxFlowType>
  32. struct Dinic {
  33.     int n, s, t;
  34.     struct Edge {
  35.         int to, cf;
  36.         Edge(int _to, int _cf) : to(_to), cf(_cf) {}
  37.     };
  38.     vector<Edge> edge;
  39.     vector<vector<int>> edgeSet;
  40.     vector<int> d, iGr;
  41.     maxFlowType maxFlow;
  42.  
  43.     Dinic(int _n, int _s, int _t) : n(_n), s(_s), t(_t) {
  44.         edge.clear(); edge.reserve(8000000);
  45.         edgeSet.assign(n, {}); edgeSet.reserve(4000000);
  46.         maxFlow = 0;
  47.     }
  48.  
  49.     int addVertex() {
  50.         int ret = n;
  51.         ++n;
  52.         edgeSet.emplace_back(vector<int>());
  53.         return ret;
  54.     }
  55.  
  56.     void addEdge(int u, int v, int c) {
  57.         edgeSet[u].emplace_back(sz(edge)); edge.emplace_back(v, c);
  58.         edgeSet[v].emplace_back(sz(edge)); edge.emplace_back(u, 0);
  59.     }
  60.  
  61.     bool bfs() {
  62.         d.assign(n, inf); d[s] = 0;
  63.         iGr.assign(n, 0);
  64.         queue<int> q; q.emplace(s);
  65.  
  66.         while (sz(q)) {
  67.         int u = q.front(); q.pop();
  68.             for (int i : edgeSet[u]) if (d[edge[i].to] == inf && edge[i].cf) {
  69.                 d[edge[i].to] = d[u] + 1;
  70.                 q.emplace(edge[i].to);
  71.             }
  72.         }
  73.  
  74.         return d[t] != inf;
  75.     }
  76.  
  77.     int dfs(int u, int flow) {
  78.         if (u == t || !flow) return flow;
  79.  
  80.         for (; iGr[u] < sz(edgeSet[u]); ++iGr[u]) {
  81.             int i = edgeSet[u][iGr[u]];
  82.             if (d[edge[i].to] != d[u] + 1 || !edge[i].cf) continue ;
  83.  
  84.             int nxt = dfs(edge[i].to, min(flow, edge[i].cf));
  85.             if (nxt) {edge[i].cf -= nxt; edge[i ^ 1].cf += nxt; return nxt;}
  86.         }
  87.  
  88.         return 0;
  89.     }
  90.  
  91.     maxFlowType get() {
  92.         while (bfs()) {
  93.             int tmp;
  94.             while ((tmp = dfs(s, inf))) maxFlow += tmp;
  95.         }
  96.  
  97.         return maxFlow;
  98.     }
  99. };
  100. Dinic<int> dn(2, 0, 1);
  101.  
  102. struct BIT {
  103.     vector<int> a;
  104.     BIT(int n) {a.assign(n, -1);}
  105.  
  106.     void upd(int pos, int val) {
  107.         for (int i = pos; i < sz(a); i |= i + 1) {
  108.             int tmp = dn.addVertex();
  109.             dn.addEdge(tmp, val, 1);
  110.             if (~a[i])
  111.                 dn.addEdge(tmp, a[i], inf);
  112.             a[i] = tmp;
  113.         }
  114.     }
  115.     void get(int pos, int val) {
  116.         for (int i = pos; ~i; i = (i & (i + 1) ) - 1) {
  117.             if (~a[i])
  118.                 dn.addEdge(val, a[i], 1);
  119.         }
  120.     }
  121. };
  122.  
  123. int main() {
  124.     ios_base::sync_with_stdio(0); cin.tie(0);
  125.  
  126.     int nBlack; cin >> nBlack;
  127.     vector<pair<int, int>> black(nBlack);
  128.     for (int i = 0; i < nBlack; ++i)
  129.         cin >> black[i].first >> black[i].second;
  130.     sort(all(black));
  131.  
  132.     int nWhite; cin >> nWhite;
  133.     vector<pair<int, int>> white(nWhite);
  134.     vector<int> idWhite(nWhite), edge(nWhite);
  135.     for (int i = 0; i < nWhite; ++i) {
  136.         cin >> white[i].first >> white[i].second;
  137.         idWhite[i] = dn.addVertex();
  138.         edge[i] = sz(dn.edge);
  139.         dn.addEdge(dn.s, idWhite[i], 1);
  140.     }
  141.  
  142.     BIT bit(nBlack);
  143.     vector<int> orderBlack(sz(black)); iota(all(orderBlack), 0);
  144.     sort(all(orderBlack), [&](const int& i, const int& j) {
  145.         return black[i].second < black[j].second;
  146.     });
  147.     vector<int> orderWhite(sz(white)); iota(all(orderWhite), 0);
  148.     sort(all(orderWhite), [&](const int& i, const int& j) {
  149.         return white[i].second < white[j].second;
  150.     });
  151.     auto iBlack = orderBlack.begin();
  152.     for (const auto& iWhite : orderWhite) {
  153.         while (iBlack != orderBlack.end() && white[iWhite].second >= black[*iBlack].second) {
  154.             int val = dn.addVertex();
  155.             dn.addEdge(val, dn.t, 1);
  156.             bit.upd(*iBlack, val);
  157.             ++iBlack;
  158.         }
  159.  
  160.         int tmp = (int)(upper_bound(all(black), make_pair(white[iWhite].first, inf)) - black.begin()) - 1;
  161.         bit.get(tmp, idWhite[iWhite]);
  162.     }
  163.  
  164.     int curAns = dn.get();
  165.     vector<int> ans(nWhite);
  166.     for (int i = nWhite - 1; ~i; --i) {
  167.         ans[i] = curAns;
  168.         curAns -= !dn.edge[edge[i]].cf;
  169.     }
  170.  
  171.     for (const auto& i : ans)
  172.         cout << i << '\n';
  173.  
  174.     return 0;
  175. }
Success #stdin #stdout 0s 4380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Yu56dT
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!