oj.uz

Submission #607580

# Submission time Handle Problem Language Result Execution time Memory
607580 2022-07-26T20:27:02 Z chonka popa (BOI18_popa) C++17
0 / 100
 20 ms 464 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 = -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.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 464 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 416 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 420 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -