oj.uz

답안 #607573

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
607573 2022-07-26T20:19:48 Z chonka popa (BOI18_popa) C++17
0 / 100
 1000 ms 208 KB 
#include<bits/stdc++.h>
#include "popa.h"
using namespace std ;


int query ( int a , int b , int c , int d ) ;

pair < int , int > ranges[ 1007 ] ;
stack < int > s ;


int solve ( int n , int *left , int *right ) {
    for ( int i = 0 ; i < n ; ++ i ) {
        ranges[ i ] = { i , i } ;
        left[ i ] = right[ i ] = -1 ;
    }
    while ( s.empty ( ) == false ) { s.pop ( ) ; }
    s.push ( -1 ) ;
    for ( int i = 0 ; i < n ; ++ i ) {
        while ( 1 ) {
            int aux = s.top ( ) ;
            if ( aux >= 0 && query ( aux , i , i , i ) == 1 ) {
                s.pop ( ) ;
            }
            else {
                ranges[ i ].first = s.top ( ) + 1 ;
                if ( s.top ( ) != -1 ) {
                    ranges[ s.top ( ) ].second = i ;
                }
                break ;
            }
        }
        s.push ( i ) ;
    }
    int root = s.top ( ) ;
    stack < int > aux ;
    aux.push ( root ) ;
    while ( aux.empty ( ) == false ) {
        int wh = aux.top ( ) ;
        aux.pop ( ) ;
        for ( int i = 0 ; i < n ; ++ i ) {
            if ( ranges[ i ].first == ranges[ wh ].first && ranges[ i ].second == wh - 1 ) {
                left[ wh ] = i ;
            }
            if ( ranges[ i ].first == wh + 1 && ranges[ i ].second == ranges[ wh ].second ) {
                right[ wh ] = i ;
            }
        }
        if ( left[ wh ] != -1 ) {
            aux.push ( left[ wh ] ) ;
        }
        else {
            aux.push ( right[ wh ] ) ;
        }
    }
    return root ;
}

Subtask #1
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3083 ms 208 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3010 ms 208 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3017 ms 208 KB Time limit exceeded
2 Halted 0 ms 0 KB -