R620(Div.2) C.Air Conditioner

 

그리디로 풀 수있는 문제다

내가 움직일 수 있는 거리는 (손님 방문시간 - 현재시간)만큼이다

 

그럼 우린 시간순으로 정렬을하고 내가 움직일 수 있는 범위를 가지고 다니면서

만약 그 범위안에 손님이 만족하는 온도가 없다면 NO 가능하다면 YES를 출력해 줄 수 있따!

 

그리고 만족한다면 시간을 바꿔주고 왼쪽 오른쪽 범위는

각각 포함할 수 있는 최대, 최소의 거리로 해줘야한다

처음에는 만족하는 범위를 찾으려고 하다가 거꾸로 해야 쉽겠다 싶어서 주석처리하고

반대의 경우를 찾았다!

 

앞으로도 쉬운것좀 생각하자.. 어려운 방법말고..!!

 

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll q,n,m;
 
 
int main(){
   scanf(" %lld",&q);
   while(q--){
      scanf(" %lld %lld",&n,&m);
      priority_queue<pair<ll,pair<ll,ll>>> pq;
      for(ll i=0;i<n;i++){
         ll t,l,h; scanf(" %lld %lld %lld",&t,&l,&h);
         pq.push({-t,{l,h}});
      }
      ll nowTime=0,nowTemp=m,nowLeft=m,nowRight=m;
      bool answer=true;
      while(!pq.empty()){
         ll visitedTime = -pq.top().first;
         ll left = pq.top().second.first;
         ll right = pq.top().second.second;
         pq.pop();
 
         ll timeDiff = visitedTime-nowTime;
         ll tempLeft= nowLeft-timeDiff;
         ll tempRight = nowRight+timeDiff;
 
         if(tempRight<left || right <tempLeft) {
            answer= false; break;
         }else{
            nowTime = visitedTime;
            nowLeft = max(tempLeft,left);
            nowRight = min(tempRight,right);
         }
      }
      if(answer) puts("YES");
      else puts("NO");
   }
}