oj.uz

Submission #92913

# Submission time Handle Problem Language Result Execution time Memory
92913 2019-01-05T14:40:59 Z Pajaraja popa (BOI18_popa) C++17
100 / 100
 88 ms 496 KB 
#include <bits/stdc++.h>
#include "popa.h"
#define MAXN 1007
using namespace std;
int ls[MAXN],rs[MAXN],dml[MAXN],dmr[MAXN];
int rek(int lt,int rt)
{
	if(lt>rt) return -1;
	int l=lt;
	while(l<=rt && (dml[l]>lt || dmr[l]<rt))  l++;
	ls[l]=rek(lt,l-1);
	rs[l]=rek(l+1,rt);
	return l;
}
int solve(int N,int* Left,int* Right)
{
	stack<int> st;
	for(int i=0;i<N;i++)
	{
		while(!st.empty()) {if(!query(st.top(),st.top(),st.top(),i)) {dmr[st.top()]=i-1; st.pop();} else break;}
		if(!st.empty()) dml[i]=st.top()+1;
		else dml[i]=0;
		st.push(i);
	}
	while(!st.empty()) {dmr[st.top()]=N-1; st.pop();}
	int a=rek(0,N-1);
	for(int i=0;i<N;i++) Left[i]=ls[i];
	for(int i=0;i<N;i++) Right[i]=rs[i];
	return a;
}

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 248 KB Output is correct
2 Correct 9 ms 380 KB Output is correct
3 Correct 10 ms 376 KB Output is correct
4 Correct 10 ms 376 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 420 KB Output is correct
2 Correct 65 ms 372 KB Output is correct
3 Correct 45 ms 336 KB Output is correct
4 Correct 47 ms 496 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 376 KB Output is correct
2 Correct 87 ms 452 KB Output is correct
3 Correct 85 ms 464 KB Output is correct
4 Correct 84 ms 376 KB Output is correct