MinhNGUYEN2k4

Untitled

Sep 18th, 2021 (edited)
182
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define double long double
  4. #define Task "NCREC"
  5. #define READFILE freopen(Task".inp", "r", stdin)
  6. #define WRITEFILE freopen(Task".out", "w", stdout)
  7. #define double long double
  8. #define oo 0x3f3f3f3f3f
  9. #define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  10. #define mp make_pair
  11. #define pb push_back
  12. #define X first
  13. #define Y second
  14. #define watch(x) cout << (#x) << " = " << x << endl
  15. #define debug(x) cout << (#x) << " = " << x << endl
  16. #define all(x) x.begin(), x.end()
  17. #define sz(x) x.size()
  18. #define endl '\n'
  19. #define max3(a,b,c) max(max(a, b), c)
  20. #define max4(a,b,c,d) max(max(a, b), max(c, d))
  21. #define min4(a,b,c,d) min(min(a, b), min(c, d))
  22. #define debug4(a,b,c,d) watch(a);watch(b);watch(c);watch(d)
  23. #define ever (;true;)
  24. #define maxn 505
  25.  
  26. #define PI 3.14159265
  27.  
  28. using namespace std;
  29.  
  30. typedef pair < int, int > ii;
  31. typedef pair < int, ii > iii;
  32. typedef pair < ii, ii > iiii;
  33. typedef vector < int > vi;
  34. typedef vector < ii > vii;
  35. typedef vector < vi > vvi;
  36. typedef vector < iii > viii;
  37. typedef vector < vii > vvii;
  38. typedef vector < iiii > viiii;
  39. typedef vector < vvi > vvvi;
  40.  
  41. const int N = 1e5 + 5;
  42.  
  43. struct DT{
  44.     int x, y1, y2, Type, id;
  45.  
  46.     bool operator < (const DT &a){
  47.         if (x != a.x) return x < a.x;
  48.         if (Type == a.Type){
  49.             if (y1 == a.y1) return y2 < a.y2;
  50.             return y1 > a.y1;
  51.         }
  52.         return Type < a.Type;
  53.     }
  54.  
  55. };
  56.  
  57. vector < DT > SL;
  58.  
  59. int n, m;
  60.  
  61. struct RECT{
  62.     int x, y, u, v;
  63.  
  64.     friend istream &operator >> (istream &stream, RECT &a){
  65.         cin >> a.x >> a.y >> a.u >> a.v;
  66.         return stream;
  67.     }
  68.  
  69. }r[N];
  70.  
  71. struct POINT{
  72.     int x, y, k;
  73.  
  74.     friend istream &operator >> (istream &stream, POINT &a){
  75.         cin >> a.x >> a.y >> a.k;
  76.         return stream;
  77.     }
  78.  
  79. }p[N];
  80.  
  81. int st[8 * N];
  82. int lazy[8 * N];
  83.  
  84. void down(int id){
  85.     if (lazy[id] == 0) return;
  86.     st[id << 1] = lazy[id];
  87.     st[id << 1 | 1] = lazy[id];
  88.     lazy[id << 1] = lazy[id];
  89.     lazy[id << 1 | 1] = lazy[id];
  90.     lazy[id] = 0;
  91. }
  92.  
  93. void update(int u, int v, int w, int id = 1, int l = 0, int r = m + 2*n){
  94.     if (l > r || u > v || u > r || l > v) return;
  95.     if (u <= l && r <= v){
  96.         st[id] = w;
  97.         lazy[id] = w;
  98.         return;
  99.     }
  100.     down(id);
  101.     int mid = (l + r) >> 1;
  102.     update(u, v, w, id << 1, l, mid);
  103.     update(u, v, w, id << 1 | 1, mid + 1, r);
  104. }
  105.  
  106. int Get(int pos, int id = 1, int l = 0, int r = m + 2*n){
  107.     if (l > r || pos < l || pos > r) return 0;
  108.     if (l == r) return st[id];
  109.     int mid = (l + r) >> 1;
  110.     down(id);
  111.     if (pos <= mid) return Get(pos, id << 1, l, mid);
  112.     return Get(pos, id << 1 | 1, mid + 1, r);
  113. }
  114.  
  115. set < int > mySet[N];
  116. int res[N];
  117. int pre[N];
  118.  
  119. void init(){
  120.     FAST;
  121.     #ifndef ONLINE_JUDGE
  122.     READFILE;
  123.     WRITEFILE;
  124.     #endif // ONLINE_JUDGE
  125. }
  126.  
  127. void enter(){
  128.     cin >> n >> m;
  129.     vi val;
  130.     for (int i = 1; i <= n; ++i){
  131.         cin >> r[i];
  132.         val.pb(r[i].y);
  133.         val.pb(r[i].v);
  134.     }
  135.     for (int i = 1; i <= m; ++i){
  136.         cin >> p[i];
  137.         val.pb(p[i].y);
  138.     }
  139.     sort(all(val));
  140.     val.erase(unique(all(val)), val.end());
  141.     for (int i = 1; i <= n; ++i){
  142.         r[i].y = lower_bound(all(val), r[i].y) - val.begin();
  143.         r[i].v = lower_bound(all(val), r[i].v) - val.begin();
  144.         SL.pb({r[i].x, r[i].y, r[i].v, -1, i});
  145.         SL.pb({r[i].u, r[i].y, r[i].v, 1, i});
  146.     }
  147.     for (int i = 1; i <= m; ++i){
  148.         p[i].y = lower_bound(all(val), p[i].y) - val.begin();
  149.         SL.pb({p[i].x, p[i].y, p[i].y, 0, p[i].k});
  150.     }
  151. }
  152.  
  153. void Solve(){
  154.     sort(all(SL));
  155.     for (int i = 0; i < (int)SL.size(); ++i){
  156.         if (SL[i].Type == 0){
  157.             int Pos = Get(SL[i].y1);
  158.             if (Pos) mySet[Pos].insert(SL[i].id);
  159.         }
  160.         else if (SL[i].Type == -1){
  161.             int Pos = Get(SL[i].y1);
  162.             pre[SL[i].id] = Pos;
  163.             update(SL[i].y1, SL[i].y2, SL[i].id);
  164.         }
  165.         else{
  166.             res[SL[i].id] = mySet[SL[i].id].size();
  167.             int u = pre[SL[i].id];
  168.             if (u){
  169.                 int v = SL[i].id;
  170.                 if (mySet[u].size() < mySet[v].size()) swap(mySet[u], mySet[v]);
  171.                 for (int T : mySet[v]) mySet[u].insert(T);
  172.             }
  173.             update(SL[i].y1, SL[i].y2, u);
  174.         }
  175.     }
  176. }
  177.  
  178. void xuat(){
  179.     for (int i = 1; i <= n; ++i) cout << res[i] << endl;
  180. }
  181.  
  182. signed main(){
  183.     init();
  184.     enter();
  185.     Solve();
  186.     xuat();
  187.     return 0;
  188. }
  189.  
RAW Paste Data