| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 152095 | nicolaalexandra | popa (BOI18_popa) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include "popa.h"
#include <cstring>
#define DIM 1010
using namespace std;
int Left[DIM],Right[DIM],t[DIM];
int solve (int n, int *Left, int *Right){
int T,n,i;
cin>>T;
for (;T--;){
cin>>n;
memset (Left,-1,sizeof Left);
memset (Right,-1,sizeof Right);
memset (t,-1,sizeof t);
/// 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;
}