제출 #255152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
255152		amoo_safar	popa (BOI18_popa)	C++14	100 / 100	122 ms	512 KiB

popa

// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#ifndef safar
#include "popa.h"
#endif


using namespace std;


const int N = 1e3 + 10;

#ifdef safar
int query(int a, int b, int c, int d){ return 1; }
#endif

stack<int> st;

int L[N], R[N];
int lc[N], rc[N];
int Solve(int l, int r){
	if(r - l < 1) return -1;

	int idx = -1;
	for(int i = l; i < r; i++){
		if(L[i] < l && r <= R[i]) idx = i;
	}
	assert(idx != -1);

	lc[idx] = Solve(l, idx);
	rc[idx] = Solve(idx + 1, r);
	return idx;
}


int solve(int n, int *left, int *right){
	
	memset(lc, -1, sizeof lc);
	memset(rc, -1, sizeof rc);

	fill(R, R + n, n);
	while(!st.empty()) st.pop();

	for(int i = 0; i < n; i++){
		while(!st.empty()){
			if(query(st.top(), st.top(), st.top(), i) == 0){
				R[st.top()] = i;
				st.pop();
			} else break;
		}
		L[i] = (st.empty() ? -1 : st.top());
		st.push(i);
	}

	int res = Solve(0, n);
	for(int i = 0; i < n; i++) left[i] = lc[i];
	for(int i = 0; i < n; i++) right[i] = rc[i];

	return res;
}

#ifdef safar
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	return 0;
}
#endif

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