Codeforces Round #805 (Div. 3) - C

문제 출처:

https://codeforces.com/contest/1702/problem/C

 

문제 분석:

예제로 보는것이 이해가 편하다

3 7 1 5 1 4

다음과 같이 기차가 가는 동선이 주어지는데 (좌에서 우로 만 이동한다.)

이후에 쿼리가 주어진다.

7 1  7->1로 갈 수 있는가? NO

1 5  1->5로 갈 수 있는가? YES

이때 정수의 범위가 10^9 이고 쿼리의 개수도 10^9까지 들어온다.

 

문제 해결:

처음에는 indexing으로 어떻게 될 것 같았는데 int범위가 너무  커서 불가능 할거라고 판단하여

map을 이용하여 두개만을 저장했다. 

가장 먼저 나오는 정류장과 가장 나중에 나오는 정류장.

이것만 가지고 갈 수 있는 여부를 확인 할 수 있기 때문이다.

 

내 소스코드:

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <cstring>
#include <list>
#include <set>
#include <string.h>
#include <map>
#include <limits.h>
#include <stdlib.h>
#include <typeinfo>
#include <bitset>
 
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
 
const int INF = 987654321;
 
int testcase;
 
 
int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> testcase;
 
    while (testcase--)
    {
        map<int, pair<int, int>> m;
        int a, b;
 
        cin >> a >> b;
        rep1(i, a)
        {
            int tmp;
            cin >> tmp;
            if(m[tmp].first == 0)
                m[tmp] = {i,i};
            else
                m[tmp] = { min(i,m[tmp].first),max(i,m[tmp].second) };
        }
 
        rep(i, b)
        {
            int c, d;
            cin >> c >> d;
            if (m[c].first == 0 || m[d].first == 0)
            {
                cout << "NO\n";
                continue;
            }
 
            if (m[c].first < m[d].second)
            {
                cout << "YES\n";
            }
            else
            {
                cout << "NO\n";
            }
        }
    }
 
 
    return 0;
}

 

고찰:

이문제도 범위 떄문에 생각을 잘못해서 TLE 여러번 내고

코드 여러번 수정해서 구현해내느라 시간을 많이 뺏긴것 같다.