oj.uz

Submission #1026639

# Submission time Handle Problem Language Result Execution time Memory
1026639 2024-07-18T08:56:38 Z lovrot Long Mansion (JOI17_long_mansion) C++17
100 / 100
 409 ms 83660 KB 
#include <cstdio>
#include <vector>
#include <set>
#include <cassert>
#include <algorithm> 
#include <cstring> 

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int LOG = 19;
const int N = 1 << LOG;
const int OO = 2e9 + 10;

int n, c[N];
vector<int> klj[N];

int lst[N], lf[N], rg[N];
int L[N], R[N];
vector<int> g[N];
set<int> act, s;

int t[2 * N];

void update(int u, int w) { 
	u += N;
	t[u] = w;
	for(u >>= 1; u; u >>= 1) { 
		t[u] = max(t[2 * u], t[2 * u + 1]);
	}
}

int query(int l, int r, int w, int u = 1, int lo = 0, int hi = N) {
	if(r <= lo || hi <= l || t[u] < w) { return -1; }
	if(lo + 1 == hi) { return lo; }
	int mi = (lo + hi) / 2;	
	int res = query(l, r, w, 2 * u + 1, mi, hi);
	if(res == -1) { return query(l, r, w, 2 * u, lo, mi); }
	return res;
}

int main() { 
	scanf("%d", &n);
	for(int i = 1; i < n; ++i) { 
		scanf("%d", c + i);
	}
	for(int i = 1; i <= n; ++i) { 
		int b; scanf("%d", &b);
		for(; b--; ) { 
			int x; scanf("%d", &x);
			klj[i].PB(x);
		}
	}

	lf[n + 1] = lf[1] = 0;
	g[0].PB(n + 1);
	g[0].PB(1);
	for(int i = 1; i <= n; ++i) { 
		if(i > 1) {
			lf[i] = lst[c[i -  1]];
			g[lf[i]].PB(i);
		}
		for(int x : klj[i]) { 
			lst[x] = i;
		}
	}

	for(int i = 1; i <= n; ++i) { 
		lst[i] = n + 1;
	}
	rg[0] = rg[n] = n + 1;
	for(int i = n; i >= 1; --i) { 
		if(i < n) { 
			rg[i] = lst[c[i]];
		}
		for(int x : klj[i]) { 
			lst[x] = i;
		}
	}

	for(int x : g[0]) { 
		act.insert(x);
	}

	for(int i = 1; i <= n; ++i) {
		if(act.find(i) != act.end()) { 
			act.erase(i);
		} else if(s.find(i) != s.end()) { 
			s.erase(i);
		}

		update(i - 1, rg[i - 1]);
		for(; !act.empty() && *(act.begin()) <= rg[i - 1]; act.erase(act.begin())) { 
//			printf("a->s %d\n", *act.begin());
			s.insert(*act.begin());
		}

		assert(!s.empty());
		R[i] = *s.begin();
		L[i] = query(lf[R[i]], n + 1, R[i]);
//		printf("%d %d (%d, %d)\n", L[i], R[i], lf[i], rg[i]);

		for(int x : g[i]) {
			act.insert(x);
		}
	}

	int q; scanf("%d", &q);
	for(; q--; ) { 
		int x, y; scanf("%d%d", &x, &y);
		printf("%s\n", L[x] < y && y < R[x] ? "YES" : "NO");
	}
	return 0;
}

Compilation message

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
long_mansion.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%d", c + i);
      |   ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:54:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   int b; scanf("%d", &b);
      |          ~~~~~^~~~~~~~~~
long_mansion.cpp:56:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |    int x; scanf("%d", &x);
      |           ~~~~~^~~~~~~~~~
long_mansion.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
long_mansion.cpp:116:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |   int x, y; scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 39512 KB Output is correct
2 Correct 9 ms 39628 KB Output is correct
3 Correct 8 ms 39768 KB Output is correct
4 Correct 8 ms 39660 KB Output is correct
5 Correct 7 ms 39516 KB Output is correct
6 Correct 7 ms 39516 KB Output is correct
7 Correct 10 ms 39664 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 39512 KB Output is correct
2 Correct 9 ms 39628 KB Output is correct
3 Correct 8 ms 39768 KB Output is correct
4 Correct 8 ms 39660 KB Output is correct
5 Correct 7 ms 39516 KB Output is correct
6 Correct 7 ms 39516 KB Output is correct
7 Correct 10 ms 39664 KB Output is correct
8 Correct 81 ms 45392 KB Output is correct
9 Correct 89 ms 45396 KB Output is correct
10 Correct 83 ms 45760 KB Output is correct
11 Correct 82 ms 46128 KB Output is correct
12 Correct 77 ms 44968 KB Output is correct
13 Correct 76 ms 45648 KB Output is correct
14 Correct 76 ms 45488 KB Output is correct
15 Correct 87 ms 45532 KB Output is correct
16 Correct 74 ms 45396 KB Output is correct
17 Correct 76 ms 45392 KB Output is correct
18 Correct 78 ms 45652 KB Output is correct
19 Correct 76 ms 45492 KB Output is correct
20 Correct 78 ms 45392 KB Output is correct
21 Correct 77 ms 45284 KB Output is correct
22 Correct 78 ms 45396 KB Output is correct
23 Correct 81 ms 45256 KB Output is correct
24 Correct 109 ms 45392 KB Output is correct
25 Correct 80 ms 45396 KB Output is correct
26 Correct 80 ms 45396 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 54084 KB Output is correct
2 Correct 153 ms 54100 KB Output is correct
3 Correct 147 ms 53844 KB Output is correct
4 Correct 158 ms 54100 KB Output is correct
5 Correct 163 ms 54100 KB Output is correct
6 Correct 135 ms 53588 KB Output is correct
7 Correct 131 ms 53668 KB Output is correct
8 Correct 153 ms 53584 KB Output is correct
9 Correct 125 ms 53584 KB Output is correct
10 Correct 133 ms 53844 KB Output is correct
11 Correct 124 ms 53832 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 39512 KB Output is correct
2 Correct 9 ms 39628 KB Output is correct
3 Correct 8 ms 39768 KB Output is correct
4 Correct 8 ms 39660 KB Output is correct
5 Correct 7 ms 39516 KB Output is correct
6 Correct 7 ms 39516 KB Output is correct
7 Correct 10 ms 39664 KB Output is correct
8 Correct 81 ms 45392 KB Output is correct
9 Correct 89 ms 45396 KB Output is correct
10 Correct 83 ms 45760 KB Output is correct
11 Correct 82 ms 46128 KB Output is correct
12 Correct 77 ms 44968 KB Output is correct
13 Correct 76 ms 45648 KB Output is correct
14 Correct 76 ms 45488 KB Output is correct
15 Correct 87 ms 45532 KB Output is correct
16 Correct 74 ms 45396 KB Output is correct
17 Correct 76 ms 45392 KB Output is correct
18 Correct 78 ms 45652 KB Output is correct
19 Correct 76 ms 45492 KB Output is correct
20 Correct 78 ms 45392 KB Output is correct
21 Correct 77 ms 45284 KB Output is correct
22 Correct 78 ms 45396 KB Output is correct
23 Correct 81 ms 45256 KB Output is correct
24 Correct 109 ms 45392 KB Output is correct
25 Correct 80 ms 45396 KB Output is correct
26 Correct 80 ms 45396 KB Output is correct
27 Correct 159 ms 54084 KB Output is correct
28 Correct 153 ms 54100 KB Output is correct
29 Correct 147 ms 53844 KB Output is correct
30 Correct 158 ms 54100 KB Output is correct
31 Correct 163 ms 54100 KB Output is correct
32 Correct 135 ms 53588 KB Output is correct
33 Correct 131 ms 53668 KB Output is correct
34 Correct 153 ms 53584 KB Output is correct
35 Correct 125 ms 53584 KB Output is correct
36 Correct 133 ms 53844 KB Output is correct
37 Correct 124 ms 53832 KB Output is correct
38 Correct 375 ms 73040 KB Output is correct
39 Correct 405 ms 77908 KB Output is correct
40 Correct 307 ms 66388 KB Output is correct
41 Correct 322 ms 78680 KB Output is correct
42 Correct 135 ms 54868 KB Output is correct
43 Correct 149 ms 54856 KB Output is correct
44 Correct 181 ms 63948 KB Output is correct
45 Correct 181 ms 64036 KB Output is correct
46 Correct 190 ms 64336 KB Output is correct
47 Correct 136 ms 55056 KB Output is correct
48 Correct 130 ms 54852 KB Output is correct
49 Correct 183 ms 64056 KB Output is correct
50 Correct 195 ms 63960 KB Output is correct
51 Correct 182 ms 64332 KB Output is correct
52 Correct 234 ms 64704 KB Output is correct
53 Correct 364 ms 73856 KB Output is correct
54 Correct 409 ms 83660 KB Output is correct
55 Correct 340 ms 73820 KB Output is correct