oj.uz

Submission #607587

# Submission time Handle Problem Language Result Execution time Memory
607587 2022-07-26T20:42:01 Z chonka popa (BOI18_popa) C++17
100 / 100
 109 ms 412 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 ] ;
vector < int > v ;


int solve ( int n , int *Left , int *Right ) {
    for ( int i = 0 ; i < n ; ++ i ) {
        ranges[ i ] = { i , i } ;
        Left[ i ] = Right[ i ] = -1 ;
    }
    v.clear ( ) ;
    v.push_back ( -1 ) ;
    for ( int i = 0 ; i < n ; ++ i ) {
        while ( 1 ) {
            int aux = v.back ( ) ;
            if ( aux >= 0 && query ( aux , i , i , i ) == 1 ) {
                v.pop_back ( ) ;
            }
            else {
                ranges[ i ].first = aux + 1 ;
                for ( auto y : v ) {
                    if ( y != -1 ) {
                        ranges[ y ].second = i ;
                    }
                }
                break ;
            }
        }
        v.push_back ( 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
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 208 KB Output is correct
2 Correct 8 ms 208 KB Output is correct
3 Correct 10 ms 208 KB Output is correct
4 Correct 10 ms 208 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 308 KB Output is correct
2 Correct 81 ms 308 KB Output is correct
3 Correct 62 ms 292 KB Output is correct
4 Correct 109 ms 296 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 304 KB Output is correct
2 Correct 106 ms 336 KB Output is correct
3 Correct 89 ms 412 KB Output is correct
4 Correct 67 ms 300 KB Output is correct