oj.uz

Submission #255152

# Submission time Handle Problem Language Result Execution time Memory
255152 2020-07-31T12:01:22 Z amoo_safar popa (BOI18_popa) C++14
100 / 100
 122 ms 512 KB 
// 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.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 384 KB Output is correct
2 Correct 10 ms 384 KB Output is correct
3 Correct 12 ms 384 KB Output is correct
4 Correct 15 ms 384 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 424 KB Output is correct
2 Correct 94 ms 424 KB Output is correct
3 Correct 61 ms 424 KB Output is correct
4 Correct 107 ms 512 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 424 KB Output is correct
2 Correct 68 ms 424 KB Output is correct
3 Correct 122 ms 424 KB Output is correct
4 Correct 95 ms 396 KB Output is correct