Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std ;
- #ifndef ONLINE_JUDGE
- #include "debugger.cpp"
- #else
- #define debug(...)
- #define debugArr(...)
- #define show(...)
- #endif
- template<typename... T>void read(T&... args) {((cin >> args), ...);}
- template<typename... T>void print(T&&... args) {((cout << args ), ...);}
- template <class T> using V = vector<T>;
- #define pb push_back
- #define int long long
- typedef long long ll ; typedef array<int, 2> pi ; typedef vector<int> vi ;
- #define len(v) (int)v.size()
- #define FOR( i , debut, fin) for( ll i = debut ; i<fin ; i++ )
- #define all(x) x.begin(), x.end()
- #define getunique(vt) vt.erase(unique(all(vt)), vt.end())
- void YES(bool x) { if (x) cout << ("Yes\n"); else cout << ("No\n"); }
- void input_output();
- template <typename node>
- struct SegTree {
- vector<node> tree;
- vector<node> lazy;
- int p, k;
- int n , neutral = 0;;
- void apply(int id, int ns, int ne, int v) {
- tree[id] += v;
- lazy[id] += v;
- }
- node mrg(const node &l, const node &r) {
- node res;
- res = max(l, r);
- return res;
- }
- void pull(int id, int ns, int ne) {
- int l = 2 * id + 1;
- int r = l + 1;
- tree[id] = mrg(tree[l], tree[r]);
- }
- void push(int id, int ns, int ne) {
- if (lazy[id] != 0 && ns != ne) {
- int l = 2 * id + 1;
- int r = l + 1;
- int md = ns + (ne - ns) / 2;
- apply(l, ns, md, lazy[id]);
- apply(r, md + 1, ne, lazy[id]);
- lazy[id] = 0;
- }
- }
- node query_MX(int qs, int qe, int id, int ns, int ne) {
- if (qs > ne || qe < ns) return 0;
- if (qs <= ns && qe >= ne) {
- return tree[id];
- }
- push(id, ns, ne);
- int l = 2 * id + 1;
- int r = l + 1;
- int md = ns + (ne - ns) / 2;
- node res;
- node rl = query_MX(qs, qe, l, ns, md);
- node rr = query_MX(qs, qe, r, md + 1, ne);
- res = max(rl,rr);
- pull(id, ns, ne);
- return res;
- }
- template <typename M>
- void update(int qs, int qe, int id, int ns, int ne, const M &v) {
- if (qs > ne || qe < ns) return;
- if (qs <= ns && qe >= ne) {
- apply(id, ns, ne, v);
- return;
- }
- push(id, ns, ne);
- int l = 2 * id + 1;
- int r = l + 1;
- int md = ns + (ne - ns) / 2;
- update(qs, qe, l, ns, md, v);
- update(qs, qe, r, md + 1, ne, v);
- pull(id, ns, ne);
- }
- SegTree(int _n) {
- n = _n;
- tree.assign(4 * n , 0LL);
- lazy.assign(4 * n , 0LL );
- }
- node query(int qs, int qe) {
- return query(qs, qe, 0, 0, n - 1);
- }
- node query_MX(int qs, int qe) {
- return query_MX(qs, qe, 0, 0, n - 1);
- }
- template <typename M>
- void update(int qs, int qe, const M &v) {
- update(qs, qe, 0, 0, n - 1, v);
- }
- };
- const int N = 1e3 + 1 ;
- void solve(){
- int n , q ;
- read ( n , q );
- vector<vector<pi>> inter (n+5);
- for (int i = 0 ; i < q ;i++ ){
- int x , l , r ;
- read ( x, l ,r );
- inter[x].push_back({l,r});
- }
- int cte = 0 ;
- for (int i = 1 ; i <= n ; i++ ){
- if ( inter[i].size() == 0 ) continue;
- sort(all(inter[i]));
- SegTree<int>checker(N);
- bool wecandelete1 = false , no_needtodel = false ;
- for ( int j = 0; j < len(inter[i]); j++ ){
- int Lhere = inter[i][j][0];
- int Rhere = inter[i][j][1];
- checker.update(Lhere , Rhere , 1 );
- }
- int qq = checker.query_MX(1,N);
- if ( qq == 1 ) no_needtodel = true;
- for ( int j = 0; j < len(inter[i]); j++ ){
- int Lhere = inter[i][j][0];
- int Rhere = inter[i][j][1];
- checker.update(Lhere , Rhere , -1 );
- int qdfd = checker.query_MX(1,N);
- if ( qdfd <= 1 ) wecandelete1 = true;
- checker.update(Lhere , Rhere , 1 );
- }
- if ( no_needtodel) continue;
- if ( wecandelete1) cte++ ;
- else cte = 10 ;
- }
- if(cte > 1) cout << "NO" << "\n";
- else cout << "YES" << "\n";
- }
- int32_t main() {
- input_output();
- int t = 1;
- cin >> t;
- for ( int i = 1 ; i <= t ; i++ ){
- show("------- Case " , i, "------- : \n" );
- solve();
- show("\n---------------------- .\n \n ");
- }
- double Time_elapsed= 1.0 * clock() / CLOCKS_PER_SEC ;
- debug(Time_elapsed);
- }
- void input_output() {
- cout.tie(0), cin.tie(0), ios_base::sync_with_stdio(0) ;
- cout << fixed << setprecision(14) ;
- cerr << fixed << setprecision(14) ;
- #ifndef ONLINE_JUDGE
- freopen("inp.txt", "r", stdin); freopen("out.txt", "w", stdout); freopen("err.txt", "w", stderr);
- #endif
- }
Advertisement
Add Comment
Please, Sign In to add comment