Submission #550300

#	Time	Username	Problem	Language	Result	Execution time	Memory
550300		LucaDantas	Long Mansion (JOI17_long_mansion)	C++17	25 / 100	391 ms	45484 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 5e5+10;

int l[maxn], r[maxn];

int edge_sweep_l[maxn], edge_sweep_r[maxn];

vector<int> keys[maxn];

bool tem(int x, int y, int cor) {
	// return 1 if there is some element with color 'cor' inside the open interval ]x, y[
	auto it = upper_bound(keys[cor].begin(), keys[cor].end(), x);
	return it != keys[cor].end() && *it < y;
}

int main() {
	int n; scanf("%d", &n);

	for(int i = 1; i < n; i++) {
		int c; scanf("%d", &c);
		edge_sweep_l[i] = edge_sweep_r[i+1] = c;
	}

	for(int i = 1; i <= n; i++) {
		int a, b; scanf("%d", &b);
		while(b--) {
			scanf("%d", &a);
			keys[a].push_back(i);
		}
	}

	// for(i = {0, n-1}) -> defino l[i]
	// for(i = {n-1, 0}) -> defino r[i] usando l[i], e também redefino l[i] overextending it
	
	l[1] = 0, r[n] = n+1; // the color of the edges are defined from [1, n] so we'll never be able to open c[0] and c[n+1] since they're 0
	int cnt = 0;
	for(int i = 1; i <= n; i++) {
		l[i] = i-1;
		while(tem(l[i], i+1, edge_sweep_l[l[i]]))
			l[i] = l[l[i]], assert(++cnt <= maxn);
	}

	for(int i = n; i >= 1; i--) {
		r[i] = i+1;
		bool foi = 1;
		while(foi) {
			foi = 0;
			while(tem(l[i], r[i], edge_sweep_l[l[i]]))
				l[i] = l[l[i]], assert(++cnt <= 2*maxn);
			while(tem(l[i], r[i], edge_sweep_r[r[i]]))
				r[i] = r[r[i]], foi = 1, assert(++cnt <= 2*maxn);
		}
	}

	int q; scanf("%d", &q);
	while(q--) {
		int x, y; scanf("%d %d", &x, &y);
		puts(y > l[x] && y < r[x] ? "YES" : "NO");
	}
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  int n; scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
long_mansion.cpp:22:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |   int c; scanf("%d", &c);
      |          ~~~~~^~~~~~~~~~
long_mansion.cpp:27:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   int a, b; scanf("%d", &b);
      |             ~~~~~^~~~~~~~~~
long_mansion.cpp:29:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |    scanf("%d", &a);
      |    ~~~~~^~~~~~~~~~
long_mansion.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
long_mansion.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   int x, y; scanf("%d %d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 0 / 75