Guest User

G

a guest
Aug 27th, 2024
278
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.90 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std ;
  3. #ifndef ONLINE_JUDGE
  4. #include "debugger.cpp"
  5. #else
  6. #define debug(...)
  7. #define debugArr(...)
  8. #define show(...)
  9. #endif
  10. template<typename... T>void read(T&... args) {((cin >> args), ...);}
  11. template<typename... T>void print(T&&... args) {((cout << args ), ...);}
  12. template <class T> using V = vector<T>;
  13. #define pb push_back
  14. #define int long long  
  15. typedef long long ll ; typedef array<int, 2> pi ; typedef vector<int> vi ;
  16. #define len(v) (int)v.size()
  17. #define FOR( i , debut,  fin) for( ll i = debut ; i<fin ; i++   )
  18. #define all(x) x.begin(), x.end()
  19. #define getunique(vt)  vt.erase(unique(all(vt)), vt.end())
  20. void YES(bool x) { if (x) cout << ("Yes\n"); else cout << ("No\n"); }
  21.  
  22. void input_output();
  23. template <typename node>
  24. struct SegTree {
  25.     vector<node> tree;
  26.     vector<node> lazy;
  27.     int p, k;
  28.     int n , neutral = 0;;
  29.  
  30.     void apply(int id, int ns, int ne, int v) {
  31.         tree[id] += v;
  32.         lazy[id] += v;
  33.     }
  34.     node mrg(const node &l, const node &r) {
  35.         node res;
  36.         res = max(l,  r);
  37.         return res;
  38.     }
  39.     void pull(int id, int ns, int ne) {
  40.         int l = 2 * id + 1;
  41.         int r = l + 1;
  42.         tree[id] = mrg(tree[l], tree[r]);
  43.     }
  44.  
  45.     void push(int id, int ns, int ne) {
  46.         if (lazy[id] != 0  && ns != ne) {
  47.             int l = 2 * id + 1;
  48.             int r = l + 1;
  49.             int md = ns + (ne - ns) / 2;
  50.             apply(l, ns, md, lazy[id]);
  51.             apply(r, md + 1, ne, lazy[id]);
  52.             lazy[id] = 0;
  53.         }
  54.     }
  55.  
  56.  
  57.     node query_MX(int qs, int qe, int id, int ns, int ne) {
  58.         if (qs > ne || qe < ns) return 0;
  59.  
  60.         if (qs <= ns && qe >= ne) {
  61.             return tree[id];
  62.         }
  63.         push(id, ns, ne);
  64.         int l = 2 * id + 1;
  65.         int r = l + 1;
  66.         int md = ns + (ne - ns) / 2;
  67.         node res;
  68.        
  69.         node rl = query_MX(qs, qe, l, ns, md);
  70.         node rr = query_MX(qs, qe, r, md + 1, ne);
  71.         res = max(rl,rr);
  72.            
  73.         pull(id, ns, ne);
  74.         return res;
  75.     }
  76.  
  77.  
  78.     template <typename M>
  79.     void update(int qs, int qe, int id, int ns, int ne, const M &v) {
  80.         if (qs > ne || qe < ns) return;
  81.         if (qs <= ns && qe >= ne) {
  82.             apply(id, ns, ne, v);
  83.             return;
  84.         }
  85.         push(id, ns, ne);
  86.         int l = 2 * id + 1;
  87.         int r = l + 1;
  88.         int md = ns + (ne - ns) / 2;
  89.         update(qs, qe, l, ns, md, v);
  90.         update(qs, qe, r, md + 1, ne, v);
  91.         pull(id, ns, ne);
  92.     }
  93.     SegTree(int _n) {
  94.         n = _n;
  95.         tree.assign(4 * n , 0LL);
  96.         lazy.assign(4 * n ,  0LL );
  97.     }
  98.     node query(int qs, int qe) {
  99.         return query(qs, qe, 0, 0, n - 1);
  100.     }
  101.     node query_MX(int qs, int qe) {
  102.         return query_MX(qs, qe, 0, 0, n - 1);
  103.     }
  104.  
  105.     template <typename M>
  106.     void update(int qs, int qe, const M &v) {
  107.         update(qs, qe, 0, 0, n - 1, v);
  108.     }
  109. };
  110. const int N = 1e3 + 1  ;
  111.  
  112. void solve(){
  113.     int n , q ;
  114.     read ( n , q );
  115.     vector<vector<pi>> inter (n+5);
  116.     for (int i = 0 ; i  < q ;i++ ){
  117.         int x , l , r ;
  118.         read ( x, l ,r );
  119.         inter[x].push_back({l,r});
  120.     }
  121.     int cte = 0 ;
  122.     for  (int i = 1 ;  i <= n ; i++  ){
  123.         if ( inter[i].size() == 0 ) continue;
  124.         sort(all(inter[i]));
  125.         SegTree<int>checker(N);
  126.  
  127.         bool wecandelete1 = false , no_needtodel = false ;
  128.         for ( int j = 0; j  < len(inter[i]);  j++ ){
  129.             int Lhere = inter[i][j][0];
  130.             int Rhere = inter[i][j][1];
  131.             checker.update(Lhere , Rhere , 1  );
  132.         }
  133.         int qq = checker.query_MX(1,N);
  134.         if ( qq == 1 ) no_needtodel = true;
  135.  
  136.         for ( int j = 0; j  < len(inter[i]);  j++ ){
  137.             int Lhere = inter[i][j][0];
  138.             int Rhere = inter[i][j][1];
  139.             checker.update(Lhere , Rhere , -1  );
  140.             int qdfd = checker.query_MX(1,N);
  141.             if ( qdfd <= 1 ) wecandelete1 = true;
  142.             checker.update(Lhere , Rhere , 1  );
  143.  
  144.         }
  145.         if ( no_needtodel) continue;
  146.         if ( wecandelete1) cte++ ;
  147.         else cte = 10 ;
  148.  
  149.     }
  150.     if(cte > 1) cout << "NO" << "\n";
  151.     else cout << "YES" << "\n";
  152.  
  153. }
  154.    
  155.  
  156. int32_t main() {
  157.     input_output();
  158.     int t = 1;
  159.     cin >> t;
  160.     for ( int i = 1 ; i <= t ; i++ ){
  161.         show("------- Case " , i, "------- : \n" );
  162.         solve();
  163.         show("\n---------------------- .\n \n ");      
  164.     }    
  165.     double Time_elapsed= 1.0 * clock() / CLOCKS_PER_SEC ;
  166.     debug(Time_elapsed);
  167.        
  168. }
  169.  
  170.  
  171. void input_output() {
  172.     cout.tie(0), cin.tie(0), ios_base::sync_with_stdio(0) ;  
  173.     cout << fixed << setprecision(14) ;
  174.     cerr << fixed << setprecision(14) ;
  175.     #ifndef ONLINE_JUDGE
  176.     freopen("inp.txt", "r", stdin); freopen("out.txt", "w", stdout); freopen("err.txt", "w", stderr);
  177.     #endif
  178. }
Advertisement
Add Comment
Please, Sign In to add comment