fork download
copy 
  1. #include <bits/stdc++.h>
  2. /* 
  3.  Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live.
  4.  — Rick Osborne
  5.   */
  6. using namespace std;
  7. typedef pair <int,int> PII;
  8. typedef vector <int> VI; 
  9. typedef vector < PII > VPII;
  10. int main()
  11. {
  12.     int tc;
  13.     scanf("%d",&tc);
  14. 		while (tc--)
  15.     {
  16.         int m, n;
  17.         scanf("%d %d",&m, &n);
  18. 				VPII segm;
  19.         for(int i=0;i<n;i++)
  20.         {
  21.             int st, en;
  22.             scanf("%d %d",&st, &en);
  23.             if(st<=en)
  24.             {
  25.                 segm.push_back(make_pair(st,en));
  26.                 segm.push_back(make_pair(st+m,en+m));
  27.             }
  28.             else
  29.                 segm.push_back(make_pair(st,en+m));
  30.         }
  31. 				if(n>m)
  32.         {
  33.             puts("NO");
  34.             continue;
  35.         }
  36.         sort(segm.begin(),segm.end());
  37.  
  38. 				int T=0;
  39.         int i=0;
  40.         set < PII > que;
  41.         bool ok = true;
  42.         while(true)
  43.         {
  44.             if(que.empty())
  45.             {
  46.                 if(i==segm.size())
  47.                     break;
  48.                 else
  49.                     T = segm[i].first;
  50.             }
  51.  
  52. 						while(i<segm.size() && segm[i].first==T)
  53.             {
  54.                 que.insert(make_pair(segm[i].second,i));
  55.                 i++;
  56.             }
  57.  
  58. 						int ind = que.begin()->second;
  59.             que.erase(que.begin());
  60.  
  61. 						if(!(T>=segm[ind].first && T<=segm[ind].second))
  62.             {
  63.                 ok = false;
  64.                 break;
  65.             }
  66.             T++;
  67.         }
  68.         puts(ok?"YES":"NO");
  69.     }
  70. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
2
4 3
0 1
1 2
2 0
5 5
0 0
1 2
2 3
4 4
4 0
stdout
copy 
YES
NO
https://ideone.com/5Xb6xw
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!