Submission #70047

#	Time	Username	Problem	Language	Result	Execution time	Memory
70047		3zp	popa (BOI18_popa)	C++14	100 / 100	103 ms	704 KiB

popa

#include<bits/stdc++.h>
#include "popa.h"
using namespace std;
int l[1009], r[1009], A[1009];
int SOLVE(int le, int ri, int *Left, int *Right){
    if(le > ri) return -1;
    for(int i = le; i <= ri; i++){
        if(l[i] <= le && r[i] >= ri){
            int A = SOLVE(le, i - 1, Left, Right);
            int B = SOLVE(i + 1, ri, Left, Right);
            Left[i] = A;
            Right[i] = B;
            return i;
        }
    }
}
int solve(int N, int* Left, int* Right){
    stack<int> S;
    for(int i = 0; i < N; i++){
        while(S.size() && query(S.top(), i,i,i)){
            S.pop();
        }
        if(!S.size()) l[i] = 0;
        else l[i] = S.top() + 1;
        S.push(i);
    }
    for(int i =  0; i < N; i++){
        r[i] = N - 1;
        for (int j = i + 1; j < N; j++){
            if(l[j] <= i) {
                r[i] = j - 1;
                break;
            }
        }
     //   cout << i <<" "<<r[i]<<" "<<l[i]<<endl;
    }
    return SOLVE(0, N - 1, Left, Right);

}

Compilation message (stderr)

popa.cpp: In function 'int SOLVE(int, int, int*, int*)':
popa.cpp:16:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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