oj.uz

Submission #431554

# Submission time Handle Problem Language Result Execution time Memory
431554 2021-06-17T12:57:43 Z pavement Long Mansion (JOI17_long_mansion) C++17
10 / 100
 2714 ms 262148 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<iii, null_type, greater<iii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N, Q, X, Y, C[500005], L[500005], R[500005], SR[500005];
vector<int> rev[500005];
map<ii, ii> chc;

bool can(int x, int l, int r) { // collecting all keys from [l, r], possible to pass thru corridor x?
	auto it = lower_bound(rev[C[x]].begin(), rev[C[x]].end(), l);
	if (it != rev[C[x]].end() && *it <= r) return 1;
	return 0;
}

ii expand(int l, int r) {
	if (chc.find(mp(l, r)) != chc.end()) return chc[mp(l, r)];
	if (l > 1 && can(l - 1, l, r)) return chc[mp(l, r)] = expand(l - 1, r);
	if (r < N && can(r, l, r)) return chc[mp(l, r)] = expand(l, r + 1);
	return mp(l, r);
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i < N; i++) cin >> C[i];
	for (int i = 1, B; i <= N; i++) {
		cin >> B;
		for (int j = 0, tmp; j < B; j++) {
			cin >> tmp;
			rev[tmp].pb(i);
		}
	}
	for (int i = 1; i <= N; i++) sort(rev[i].begin(), rev[i].end());
	for (int i = N; i >= 1; i--)
		if (i < N && can(i, i, i)) {
			SR[i] = i;
			while (SR[i] < N && can(SR[i], i, SR[i])) SR[i] = SR[SR[i] + 1];
		} else SR[i] = i;
	for (int i = 1; i <= N; i++) {
		if (i > 1 && can(i - 1, i, SR[i])) {
			L[i] = L[i - 1];
			R[i] = max(R[i - 1], SR[i]);
		} else {
			L[i] = i;
			R[i] = SR[i];
		}
		tie(L[i], R[i]) = expand(L[i], R[i]);
	}
	cin >> Q;
	while (Q--) {
		cin >> X >> Y;
		cout << (L[X] <= Y && Y <= R[X] ? "YES" : "NO") << '\n';
	}
}

Compilation message

long_mansion.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main() {
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14936 KB Output is correct
2 Correct 291 ms 47036 KB Output is correct
3 Correct 1298 ms 127588 KB Output is correct
4 Correct 13 ms 12256 KB Output is correct
5 Correct 12 ms 12356 KB Output is correct
6 Correct 12 ms 12304 KB Output is correct
7 Correct 11 ms 12492 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14936 KB Output is correct
2 Correct 291 ms 47036 KB Output is correct
3 Correct 1298 ms 127588 KB Output is correct
4 Correct 13 ms 12256 KB Output is correct
5 Correct 12 ms 12356 KB Output is correct
6 Correct 12 ms 12304 KB Output is correct
7 Correct 11 ms 12492 KB Output is correct
8 Correct 191 ms 21440 KB Output is correct
9 Correct 160 ms 15664 KB Output is correct
10 Correct 461 ms 48740 KB Output is correct
11 Correct 1528 ms 124984 KB Output is correct
12 Correct 158 ms 17768 KB Output is correct
13 Correct 164 ms 13892 KB Output is correct
14 Correct 145 ms 13920 KB Output is correct
15 Correct 151 ms 14912 KB Output is correct
16 Correct 146 ms 14108 KB Output is correct
17 Correct 146 ms 14372 KB Output is correct
18 Correct 149 ms 13964 KB Output is correct
19 Correct 141 ms 13872 KB Output is correct
20 Correct 138 ms 14952 KB Output is correct
21 Correct 145 ms 14168 KB Output is correct
22 Correct 162 ms 14076 KB Output is correct
23 Correct 147 ms 14052 KB Output is correct
24 Correct 157 ms 14048 KB Output is correct
25 Correct 166 ms 14116 KB Output is correct
26 Correct 169 ms 13996 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 2714 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14936 KB Output is correct
2 Correct 291 ms 47036 KB Output is correct
3 Correct 1298 ms 127588 KB Output is correct
4 Correct 13 ms 12256 KB Output is correct
5 Correct 12 ms 12356 KB Output is correct
6 Correct 12 ms 12304 KB Output is correct
7 Correct 11 ms 12492 KB Output is correct
8 Correct 191 ms 21440 KB Output is correct
9 Correct 160 ms 15664 KB Output is correct
10 Correct 461 ms 48740 KB Output is correct
11 Correct 1528 ms 124984 KB Output is correct
12 Correct 158 ms 17768 KB Output is correct
13 Correct 164 ms 13892 KB Output is correct
14 Correct 145 ms 13920 KB Output is correct
15 Correct 151 ms 14912 KB Output is correct
16 Correct 146 ms 14108 KB Output is correct
17 Correct 146 ms 14372 KB Output is correct
18 Correct 149 ms 13964 KB Output is correct
19 Correct 141 ms 13872 KB Output is correct
20 Correct 138 ms 14952 KB Output is correct
21 Correct 145 ms 14168 KB Output is correct
22 Correct 162 ms 14076 KB Output is correct
23 Correct 147 ms 14052 KB Output is correct
24 Correct 157 ms 14048 KB Output is correct
25 Correct 166 ms 14116 KB Output is correct
26 Correct 169 ms 13996 KB Output is correct
27 Runtime error 2714 ms 262148 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -