oj.uz

Submission #550299

# Submission time Handle Problem Language Result Execution time Memory
550299 2022-04-17T20:04:29 Z LucaDantas Long Mansion (JOI17_long_mansion) C++17
0 / 100
 90 ms 33584 KB 
#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 <= n);
	}

	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*n);
			while(tem(l[i], r[i], edge_sweep_r[r[i]]))
				r[i] = r[r[i]], foi = 1, assert(++cnt <= 2*n);
		}
	}

	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

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 24532 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 24532 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 90 ms 33584 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 24532 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -