fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define debug(x) cout << #x << " = " << x << '\n'
  5. #define debug_arr(a , n) for(int i = 0 ; i < n ; i++)cerr << a[i] << " "
  6. #define debug_vector(a) for(auto it : a)cout << it << " "
  7. #define mp make_pair
  8. #define pb push_back
  9. #define ff first
  10. #define ss second
  11. #define vi vector<int>
  12. #define vll vector<ll> 
  13. #define inf 1000000000
  14. #define mod 1000000007
  15.  
  16. ll power(ll a , ll b)
  17. {
  18.     ll prod = 1;
  19.     while(b)
  20.     {
  21.         if(b&1)
  22.         prod = (prod*a)%mod;
  23.         a = (a*a)%mod;
  24.         b >>= 1;
  25.     }
  26.     return prod;
  27. }
  28. int main()
  29. {
  30.     int t;
  31.     cin >> t;
  32.     while(t--)
  33.     {
  34.         ll n , m;
  35.         cin >> n >> m;
  36.         ll point1 = m , point2 = m , flag1 = 0 , flag = 0 , cnt = 0;
  37.         vector<pair<ll , pair<ll,ll>>> p;
  38.         map<ll , vector<pair<ll,ll>>> m1;
  39.         for(int i = 0 ; i < n ; i++)
  40.         {
  41.             ll x , lb , ub;
  42.             cin >> x >> lb >> ub;
  43.             m1[x].pb({lb , ub});
  44.         }
  45.  
  46.         for(auto it : m1)
  47.         {
  48.  
  49.             ll max1 = it.ss[0].ss;
  50.             ll min1 = it.ss[0].ff;
  51.  
  52.             for(auto it1 : it.ss)
  53.             {
  54.                 // cout << it1.ff << " " << it1.ss << " ";
  55.                 max1 = min(it1.ss , max1);
  56.                 min1 = max(it1.ff , min1);
  57.             }
  58.             // cout << min1 << " " << max1 << endl;
  59.             if(min1 <= max1)
  60.             {
  61.                 p.pb({it.ff , {min1 , max1}});
  62.             }
  63.             else
  64.             {
  65.                 cout << "NO\n";
  66.                 flag1 = 1;
  67.                 break;
  68.             }
  69.  
  70.         }
  71.         if(flag1 == 1)continue;
  72.         n = p.size();
  73.  
  74.         // for(auto it : p)
  75.         // {
  76.         //     cout << it.ff << " " << it.ss.ff << " " << it.ss.ss << endl;
  77.         // }
  78.         int num = 0;
  79.         if(p[0].ff == 0)
  80.         {
  81.             num = 1;
  82.             // cout << p[0].ss.ff << " " << p[0].ss.ss << endl;
  83.             if(!(m >= p[0].ss.ff && m <= p[0].ss.ss))
  84.             {
  85.                 cout << "NO\n";
  86.                 flag1 = 1;
  87.             }
  88.             else
  89.             {
  90.                 point1 = p[0].ss.ff;
  91.                 point2 = p[0].ss.ss;
  92.             }
  93.  
  94.         }
  95.         for(int i = num ; i < n ; i++)
  96.         {
  97.             ll x , lb , ub;
  98.             x = p[i].ff;
  99.             lb = p[i].ss.ff;
  100.             ub = p[i].ss.ss;
  101.             ll max1 , min1;
  102.             // cout << point1 << " " << point2 << endl;
  103.             if(i == 0)
  104.                 max1 = max(x + point1  , x + point2), min1 = min(point2 - x , point1 - x);
  105.             else
  106.             {
  107.                 x -= p[i-1].ff;
  108.                 max1 = max(x + point1  , x + point2), min1 = min(point2 - x , point1 - x);
  109.             }
  110.  
  111.             // cout << max1 << " " << min1 << endl;
  112.             ll max2 = max1 , min2 = min1;
  113.             flag = 0;
  114.             if(ub == lb){
  115.                 if(ub <= max1 && ub > min1)
  116.                 {
  117.                     flag = 1;
  118.                     max2 = ub;
  119.                 }
  120.                 if(lb < max1 && lb >= min1)
  121.                 {
  122.                     flag = 1;
  123.                     min2 = lb;
  124.                 }
  125.             }
  126.             else
  127.             {
  128.                 if(ub <= max1 && ub >= min1)
  129.                 {
  130.                     flag = 1;
  131.                     max2 = ub;
  132.                 }
  133.                 if(lb <= max1 && lb >= min1)
  134.                 {
  135.                     flag = 1;
  136.                     min2 = lb;
  137.                 }
  138.             }
  139.  
  140.             if(flag == 0)
  141.             {
  142.                 cout << "NO\n";
  143.                 flag1 = 1;
  144.                 break;
  145.             }
  146.             point1 = max2;
  147.             point2 = min2;
  148.         }
  149.         if(flag1 == 0)
  150.         {
  151.             cout << "YES\n";
  152.         }
  153.     }
  154.     return 0;
  155. }
Time limit exceeded #stdin #stdout 5s 3655232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oEnQj4
language:
C++14 (gcc 8.3)
created:
4 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!