글 읽기 - 이진탐색했는데도 시간초과가 나네요 ㅠ

1214sw 3년 전 0

큰 테스트 케이스도 만들어보고 했는데 시간초과가 도대체 어디서 나는 걸까요? ㅠ

#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
#include <stack>

using namespace std;

int n; // 1~100,000
pair<int, int> elec_line[100'005]; //1~500,000
int arr[100'005]; //1~500,000

int max_height[100'005];
int LIS[100'005];
int top = 0;

int main()
{
    cin >> n;
    for(int i=0; i<n; i++)
    {
        int x, y;
        cin >> x >> y;
        elec_line[i] = make_pair(x, y);
    }

    sort(elec_line, elec_line + n);
    for(int i=0; i<n; i++) arr[i] = elec_line[i].second;


    // arr의 가장 긴 증가하는 부분수열을 구하자.
    LIS[0]=-1;
    for(int i=0; i<n; i++)
    {
        int loc = upper_bound(LIS, LIS+top+1, arr[i]) - LIS;
//        cout << i << " -> loc: " << loc << endl;
        if(loc == top + 1)
        {
            top++;
        }
        LIS[loc] = arr[i];
        max_height[i] = loc;

//        cout << "max_height" << endl;
//        for(int i=0; i<n; i++) cout << max_height[i] << " ";
//        cout << endl;
//
//        cout << "LIS" << endl;
//        for(int i=0; i<n; i++) cout << LIS[i] << " ";
//        cout << endl;
//
//        cout << endl;
    }

    cout << n - top << endl;

    stack<int> ans;
    for(int i=n-1; i>=0; i--)
    {
        if(max_height[i] == top)
        {
            top--;
        }
        else
        {
            ans.push(elec_line[i].first);
        }
    }
    while(!ans.empty())
    {
        cout << ans.top() << endl;
        ans.pop();
    }
}

cjy11230 2년 전 0

endl 대신 "\n"으로 쓰시고

cin 입력 속도 빠르게 해보세요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이진탐색했는데도 시간초과가 나네요 ㅠ

1214sw 3년 전 0

cjy11230 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말