Submission #1270686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270686		Alebn	popa (BOI18_popa)	C++20	100 / 100	25 ms	440 KiB

popa

#include <bits/stdc++.h>
#include "popa.h"
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using namespace std;

signed solve(signed n, signed l[], signed r[]) {
    stack<int> st;
    vector<int> p(n);
    for(int i = 0; i < n; i++) {
        l[i] = r[i] = -1;
        while(st.size() && query(st.top(), i, i, i)) st.pop();
        p[i] = (st.size() ? st.top() : -1);
        st.push(i);
    }
    int root = -1;
    stack<pii> sti;
    for(int i = n - 1; i > -1; i--) {
        while(sti.size() && sti.top().ff >= i) sti.pop();
        if(p[i] == -1 || r[p[i]] != -1) {
            if(sti.size()) {
                l[sti.top().ss] = i;
                sti.pop();
            } else {
                assert(root == -1);
                root = i;
            }
        } else r[p[i]] = i;
        sti.push({p[i], i});
    }
    return root;
}

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