글 읽기 - 2957 이진 탐색 트리

mrcamel 9년 전 0

삽입할 숫자를 t라고 하면

[1,t)에서 t와 가장 가까이 있는 수

(t,n]에서 t와 가장 가까이 있는 수

둘 중 하나의 자식이라서 이진탐색과 BIT를 써서 O( n(logn)^2 ) 안에 해결 가능 할 줄 알았는데 시간초과가 발생하네요.

300000 1 2 3 4 .. 300000 의 경우 BOJ코딩에서 300ms 정도로 통과하는데 이보다 더 느린 경우가 있을까요?

8 3 5 1 6 8 7 2 4의 경우

lv[i]	1	2	3	4	5	6	7	8
			0
			0		1
	1		0		1
	1		0		1	2
	1		0		1	2		3
	1		0		1	2	4	3
	1	2	0		1	2	4	3
	1	2	0	2	1	2	4	3

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

#define in cin
#define out cout

int n;
int lv[333333]; //깊이
int lf[333333]; //lf[i] i왼쪽에 연결된 것
int rt[333333]; // 오른쪽
int BIT[1111111]; //BIT
int BITSZ = 1;

int get(int s, int e)
{
    s = BITSZ + s - 1;
    e = BITSZ + e - 1;

    int r = 0;
    while(s<=e)
    {
        if(s%2==1) r+=BIT[s];
        if(e%2==0) r+=BIT[e];

        s=(s+1)/2;
        e=(e-1)/2;
    }

    return r;
}

void update(int n)
{
    n = BITSZ + n - 1;
    while(n)
    {
        BIT[n]++;
        n /= 2;
    }
}

int main()
{
    int n; in >> n;
    for(int i=1; i<=n; i++) lv[i] = -1;
    while(BITSZ < n) BITSZ *= 2;

    //
    long long int res = 0;
    int _t; in >> _t; lv[_t] = 0; update(_t); out << 0 << endl;
    for(int i=2; i<=n; i++)
    {
        int t; in >> t;
        
        //left
        bool flg = false;
        int pp=1, qq=t, g=-1; //[1, t) 구간에서 t로부터 가장 가까운 수를 구함
        while(pp<=qq)
        {
            int m = (pp+qq)/2;
            g = get(m, t);
            if(g==0) qq=m-1;
            else if(g>1 || lv[m] == -1 || rt[m] != 0) pp=m+1;
            else if(g == 1 && lv[m] != -1)
            {
                rt[m] = t;
                lv[t] = lv[m]+1;
                res += lv[t];
                update(t);

                flg = true;
                break;
            }
            else return -1;
        }

        if(flg) {out << res << endl; continue;}
		
        //right
        pp=t, qq=n; 
        while(pp<=qq) //(t, n] 구간에서 t로부터 가장 가까운 수를 구함
        {
            int m = (pp+qq)/2;
            g = get(t, m);
            if(g==0) pp=m+1;
            else if(g>1 || lv[m] == -1 || lf[m] != 0) qq=m-1;
            else if(g == 1 && lv[m] != -1)
            {
                lf[m] = t;
                lv[t] = lv[m]+1;
                res += lv[t];
                update(t);

                break;
            }
            else return -1;
        }

        out << res << endl;
    }

    return 0;
}

pichulia 9년 전 1

https://www.acmicpc.net/coding/view/4418

O(n*(logn)^2) 정도면 n이 300,000 일 때 잘만하면 TLE가 나올 수 있는 크기입니다....ㅠㅠ

위의 코드는 인덱스트리가 밸런스되게 (중간에 노이즈좀 넣어주고...) 데이터를 넣은 경우입니다.

데이터 만드느라 시간이 소비되서 1초가 된거같기도 한데...아무튼 이런 경우에 시간이 꽤 걸리네요

mrcamel 9년 전 0

감사합니다!

공식 홈페이지에는 map으로 O nlogn 으로 풀던데 좀 생각해봐야겠네요 ㅠㅠ

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

문제

문제

출처

ICPC

2957 이진 탐색 트리

mrcamel 9년 전 0

pichulia 9년 전 1

mrcamel 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말