Submission #104358

#	Time	Username	Problem	Language	Result	Execution time	Memory
104358		tmk	popa (BOI18_popa)	C++17	100 / 100	104 ms	512 KiB

popa

#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 / 37
• Subtask 2: 24 / 24
• Subtask 3: 39 / 39