[코드포스 Practice22] B. Chat Online

아니 왜!! 안 풀리지!!! 싶었는데 그냥 내가 예시를 잘 못 생각해서 문제였다. a, b가 2-3이고 c, d가 0-1이라 t가 2, 3이어야 한다고 생각했다. 그래서 답이 2인데 왜 3이지 계속 생각하다가 패스..

 

 

이 문제는 가능한 모든 t의 개수를 구해야 해서 복잡했다. 그런데 값이 50이 최대이다? 그래서 그냥 다 구했음. l부터 r까지 범위가 1000이라 1000번 확인하고 구간 50개 * 50개 확인하면 최대 2,500,000번 반복문을 돈다. 1초에 1~2억번까지 루프를 돌 수 있으므로 시간 내에 돌아간다.

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main() {
    int p, q, l, r;
    scanf("%d %d %d %d", &p, &q, &l, &r);
 
    vector<ii> a(p);
    vector<ii> c(q);
 
    for (int i = 0; i < p; i++)
        scanf("%d %d", &a[i].xx, &a[i].yy);
    for (int i = 0; i < q; i++)
        scanf("%d %d", &c[i].xx, &c[i].yy);
 
    int count = 0;
    for (int i = l ; i <= r; i++)
    {
        bool is_find = false;
        for (int j = 0; j < p; j++)
        {
            for (int k = 0; k < q; k++)
            {
                if (a[j].xx <= (c[k].yy + i) && (c[k].yy + i) <= a[j].yy)
                {
                    is_find = true;
                    break;
                }
                else if (a[j].xx <= (c[k].xx + i) && (c[k].xx + i) <= a[j].yy)
                {
                    is_find = true;
                    break;
                }
            }
            if (is_find)
            {
                count++;
                break;
            }
        }
    }
    
    printf("%d\n", count);
    return 0;
}

 

처음 작성한 코드이다. l부터 r까지 확인하면서 a와 c의 범위가 겹치는지 확인했다.

 

 

위 사진처럼 겹치는 부분을 확인했는데 틀렸다.. 오만 범위 테스트 했는데 도저히 모르겠어서 북님에게 물어봤더니 c가 a를 포함하는 범위를 빼먹었다고(!) 알려줬다.

 

else if ((c[k].xx + i) <= a[j].xx && a[j].yy <= (c[k].yy + i))
{
    is_find = true;
    break;
}

 

그래서 c가 a를 확인하는 부분을 추가했고 통과했다! 그리고 이렇게 범위 확인하는 부분은 조건을 아래와 같이 하면 편하다고 추천 받았다.

 

if (max(a[j].xx, (c[k].xx + i)) <= min(a[j].yy, (c[k].yy + i)))
{
    is_find = true;
    break;
}

 

 

확인하는 부분은 나중에..

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main() {
    int p, q, l, r;
    scanf("%d %d %d %d", &p, &q, &l, &r);

    vector<ii> a(p);
    vector<ii> c(q);

    for (int i = 0; i < p; i++)
        scanf("%d %d", &a[i].xx, &a[i].yy);
    for (int i = 0; i < q; i++)
        scanf("%d %d", &c[i].xx, &c[i].yy);

    int count = 0;
    for (int i = l; i <= r; i++)
    {
        bool is_find = false;
        for (int j = 0; j < p; j++)
        {
            for (int k = 0; k < q; k++)
            {
                if (max(a[j].xx, (c[k].xx + i)) <= min(a[j].yy, (c[k].yy + i)))
                {
                    is_find = true;
                    break;
                }
            }
            if (is_find)
            {
                count++;
                break;
            }
        }
    }
    
    printf("%d\n", count);
    return 0;
}

 

조건을 이렇게 바꿨다. 통과했음ㅎㅎ

 

북님 코드 확인하는 것도 나중에 할겨