oj.uz

Submission #104358

# Submission time Handle Problem Language Result Execution time Memory
104358 2019-04-05T15:28:51 Z tmk popa (BOI18_popa) C++17
100 / 100
 104 ms 512 KB 
#include<bits/stdc++.h>
#include"popa.h"
using namespace std;
#ifndef d
#define d(...)
#endif
#define st first
#define nd second
#define pb push_back
#define siz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
typedef long long LL;
typedef long double LD;
constexpr int INF=1e9+7;
constexpr LL INFL=1e18;
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

int sz[1000], l[1000], r[1000];
bool vis[1000];

pair<int, int> dfs(int a) {
	vis[a] = true;
	int mn = a, mx = a;
	if(l[a] != -1) {
		mn = dfs(l[a]).st;
		assert(query(mn, a, a, a));
	}
	if(r[a] != -1) {
		mx = dfs(r[a]).nd;
		assert(query(a, a, a, mx));
	}
	return {mn, mx};
}	

void check(int root, int n, int *L, int *R) {
	copy_n(L, n, l);
	copy_n(R, n, r);
	
	dfs(root);
	assert(all_of(vis, vis+n, [](bool x) { return x; }));
}

int solve(int n, int *L, int *R) {
	fill_n(L, n, -1);
	fill_n(R, n, -1);
	
	int cur = 0;
	stack<int> S;
	while(cur < n-1) {
		if(query(cur, cur, cur, cur+1)) {
			S.push(cur++);
		} else {
			int lst = cur;
			while(not S.empty() and query(S.top(), cur+1, cur+1, cur+1)) {
				auto tmp = S.top(); 
				S.pop();
				R[tmp] = lst;
				lst = tmp;
			}
			L[cur+1] = lst;
			++cur;
		}
	}
	while(not S.empty()) {
		auto lst = S.top();
		S.pop();
		R[lst] = cur;
		cur = lst;
	}
	
	//check(cur, n, L, R);
	return cur;
}

Subtask #1
37.0 / 37.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 444 KB Output is correct
2 Correct 87 ms 256 KB Output is correct
3 Correct 64 ms 328 KB Output is correct
4 Correct 104 ms 384 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 512 KB Output is correct
2 Correct 71 ms 324 KB Output is correct
3 Correct 83 ms 448 KB Output is correct
4 Correct 84 ms 332 KB Output is correct