oj.uz

Submission #152097

# Submission time Handle Problem Language Result Execution time Memory
152097 2019-09-06T11:21:42 Z nicolaalexandra popa (BOI18_popa) C++14
100 / 100
 111 ms 448 KB 
#include <iostream>
#include "popa.h"
#define DIM 1010
using namespace std;
//int Left[DIM],Right[DIM],t[DIM];
int solve (int n, int *Left, int *Right){
    int t[DIM];
    for (int i=0;i<n;i++)
        Left[i] = Right[i] = t[i] = -1;
    /// pt ca parcurgerea in inordine e 0..n-1, arborele are structura unui arbore binar de cautare
    /// si tot subarborele lui i contine o subsecv compacta de nr
    /// val[Left[nod]] = val[nod]-1 => pe i incerc sa l pun fix desupra lui i-1
    int rad = 0;
    for (int i=1;i<n;i++){
        int x = i-1;
        while (x >= 0 && !query(x,x,x,i)) /// cat timp x nu e radacina subarborelui
            x = t[x];

        if (x >= 0){
            /// il adaug pe i intre nodurile x si Right[x] (pt ca Left[x] e deja fixat)
            Left[i] = Right[x]; /// subarborele il plasez in stanga pt ca toate nodurile sunt mai mici decat i
            Right[x] = i;
            if (Left[i] >= 0) /// poate sa fie si -1
                t[Left[i]] = i;
            t[i] = x;

        } else { /// inseamna ca i va fi noua radacina
            Left[i] = rad;
            t[rad] = i;
            rad = i;
        }}
    return rad;
}

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 376 KB Output is correct
2 Correct 12 ms 248 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 7 ms 248 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 376 KB Output is correct
2 Correct 111 ms 248 KB Output is correct
3 Correct 63 ms 324 KB Output is correct
4 Correct 84 ms 444 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 448 KB Output is correct
2 Correct 68 ms 444 KB Output is correct
3 Correct 64 ms 376 KB Output is correct
4 Correct 73 ms 324 KB Output is correct