Submission #607580

#	Time	Username	Problem	Language	Result	Execution time	Memory
607580		chonka	popa (BOI18_popa)	C++17	0 / 100	20 ms	464 KiB

popa

#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 = -1 ;
    for ( int i = 0 ; i < n ; ++ i ) {
        if ( ranges[ i ].first == 0 && ranges[ i ].second == n - 1 ) {
            root = i ;
            break ;
        }
    }
    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 ] ) ;
        }
        if ( Right[ wh ] != -1 ) {
            aux.push ( Right[ wh ] ) ;
        }
    }
    return root ;
}

• Subtask 1: 0 / 37
• Subtask 2: 0 / 24
• Subtask 3: 0 / 39