답안 #60415 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60415	2018-07-24T06:54:58 Z	윤교준(#1744)	Long Mansion (JOI17_long_mansion)	C++11	100 / 100	2261 ms	91004 KB

long_mansion

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define revv(V) reverse(allv(V))
#define sz(V) ((int)(V).size())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const bool debug = 0;
const int MAXN = 500005;
const int MAXK = 500005;
const int MAXQ = 500005;

vector<int> G[MAXK];

int L[MAXN], R[MAXN];

vector<int> B[MAXN];
int A[MAXN];

int N, Q;

int f(int s, int e, int c) {
	return int(upper_bound(allv(G[c]), e) - upper_bound(allv(G[c]), s-1));
}

void f(int s, int e) {
	if(s == e) return;
	int m = (s+e) >> 1;
	f(s, m); f(m+1, e);

	for(int i = m, l = L[m], r = m+1; s <= i; i--) {
		if(R[i] < m || !f(L[i], R[i], A[m])) continue;
		upmin(l, L[i]);
		for(;;) {
			if(s < l && f(l, r, A[l-1])) l--;
			else if(r < e && f(l, r, A[r])) r++;
			else break;
		}
		upmin(L[i], l); upmax(R[i], r);
	}
	for(int i = m+1, l = m, r = R[m+1]; i <= e; i++) {
		if(m+1 < L[i] || !f(L[i], R[i], A[m])) continue;
		upmax(r, R[i]);
		for(;;) {
			if(s < l && f(l, r, A[l-1])) l--;
			else if(r < e && f(l, r, A[r])) r++;
			else break;
		}
		upmin(L[i], l); upmax(R[i], r);
	}
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1; i < N; i++) cin >> A[i];
	for(int i = 1, c, t; i <= N; i++) {
		for(cin >> c; c--;) {
			cin >> t;
			B[i].eb(t);
		}
	}
	for(int i = 1; i <= N; i++)
		for(int v : B[i]) G[v].eb(i);
	
	if(debug) {
		for(int i = 1; i <= N; i++) {
			printf("%d B : ", i);
			for(int v : B[i]) printf("%d ", v);
			puts("");
		}
		for(int i = 1; i <= N; i++) {
			printf("%d G : ", i);
			for(int v : G[i]) printf("%d ", v);
			puts("");
		}
	}

	{
		set<pii> CH, IH;
		for(int i = 1; i <= N; i++) {
			bool flag = false;
			for(auto it = IH.end();;) {
				if(it == IH.begin()) break; it--;
				if(f(i, i, it->second)) continue;
				flag = true;
				L[i] = it->first;
				break;
			}
			if(!flag) L[i] = 1;
			if(i < N) {
				auto it = CH.lower_bound(pii(A[i], -INF));
				if(CH.end() != it && it->first == A[i]) {
					IH.erase(pii(it->second, it->first));
					CH.erase(it);
				}
				CH.insert(pii(A[i], i+1));
				IH.insert(pii(i+1, A[i]));
			}
		}
	}
	{
		set<pii> CH, IH;
		for(int i = N; i; i--) {
			bool flag = false;
			for(auto it = IH.begin(); IH.end() != it; it++) {
				if(f(i, i, it->second)) continue;
				flag = true;
				R[i] = it->first;
				break;
			}
			if(!flag) R[i] = N;
			if(1 < i) {
				auto it = CH.lower_bound(pii(A[i-1], -INF));
				if(CH.end() != it && it->first == A[i-1]) {
					IH.erase(pii(it->second, it->first));
					CH.erase(it);
				}
				CH.insert(pii(A[i-1], i-1));
				IH.insert(pii(i-1, A[i-1]));
			}
		}
	}

	if(debug) {
		for(int i = 1; i <= N; i++)
			printf("%d ; %d %d\n", i, L[i], R[i]);
	}

	f(1, N);

	if(debug) {
		for(int i = 1; i <= N; i++)
			printf("FINAL %d ; %d %d\n", i, L[i], R[i]);
	}

	cin >> Q;
	for(int a, b; Q--;) {
		cin >> a >> b;
		puts((L[a] <= b && b <= R[a]) ? "YES" : "NO");
	}
	return 0;
}

Compilation message

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:95:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(it == IH.begin()) break; it--;
     ^~
long_mansion.cpp:95:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
     if(it == IH.begin()) break; it--;
                                 ^~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	23928 KB	Output is correct
2	Correct	34 ms	24168 KB	Output is correct
3	Correct	42 ms	24240 KB	Output is correct
4	Correct	35 ms	24240 KB	Output is correct
5	Correct	41 ms	24240 KB	Output is correct
6	Correct	35 ms	24276 KB	Output is correct
7	Correct	35 ms	24404 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	23928 KB	Output is correct
2	Correct	34 ms	24168 KB	Output is correct
3	Correct	42 ms	24240 KB	Output is correct
4	Correct	35 ms	24240 KB	Output is correct
5	Correct	41 ms	24240 KB	Output is correct
6	Correct	35 ms	24276 KB	Output is correct
7	Correct	35 ms	24404 KB	Output is correct
8	Correct	191 ms	25776 KB	Output is correct
9	Correct	165 ms	25776 KB	Output is correct
10	Correct	248 ms	25924 KB	Output is correct
11	Correct	192 ms	26260 KB	Output is correct
12	Correct	204 ms	26260 KB	Output is correct
13	Correct	194 ms	26260 KB	Output is correct
14	Correct	199 ms	26260 KB	Output is correct
15	Correct	205 ms	26260 KB	Output is correct
16	Correct	242 ms	26260 KB	Output is correct
17	Correct	198 ms	26260 KB	Output is correct
18	Correct	242 ms	26260 KB	Output is correct
19	Correct	165 ms	26260 KB	Output is correct
20	Correct	172 ms	26260 KB	Output is correct
21	Correct	135 ms	26260 KB	Output is correct
22	Correct	202 ms	26260 KB	Output is correct
23	Correct	223 ms	26260 KB	Output is correct
24	Correct	212 ms	26260 KB	Output is correct
25	Correct	165 ms	26260 KB	Output is correct
26	Correct	200 ms	26260 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	720 ms	33284 KB	Output is correct
2	Correct	750 ms	33284 KB	Output is correct
3	Correct	764 ms	33284 KB	Output is correct
4	Correct	715 ms	33284 KB	Output is correct
5	Correct	741 ms	33284 KB	Output is correct
6	Correct	800 ms	33284 KB	Output is correct
7	Correct	883 ms	33284 KB	Output is correct
8	Correct	741 ms	33284 KB	Output is correct
9	Correct	684 ms	33284 KB	Output is correct
10	Correct	786 ms	33284 KB	Output is correct
11	Correct	746 ms	33284 KB	Output is correct

Subtask #4
75.0 / 75.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	23928 KB	Output is correct
2	Correct	34 ms	24168 KB	Output is correct
3	Correct	42 ms	24240 KB	Output is correct
4	Correct	35 ms	24240 KB	Output is correct
5	Correct	41 ms	24240 KB	Output is correct
6	Correct	35 ms	24276 KB	Output is correct
7	Correct	35 ms	24404 KB	Output is correct
8	Correct	191 ms	25776 KB	Output is correct
9	Correct	165 ms	25776 KB	Output is correct
10	Correct	248 ms	25924 KB	Output is correct
11	Correct	192 ms	26260 KB	Output is correct
12	Correct	204 ms	26260 KB	Output is correct
13	Correct	194 ms	26260 KB	Output is correct
14	Correct	199 ms	26260 KB	Output is correct
15	Correct	205 ms	26260 KB	Output is correct
16	Correct	242 ms	26260 KB	Output is correct
17	Correct	198 ms	26260 KB	Output is correct
18	Correct	242 ms	26260 KB	Output is correct
19	Correct	165 ms	26260 KB	Output is correct
20	Correct	172 ms	26260 KB	Output is correct
21	Correct	135 ms	26260 KB	Output is correct
22	Correct	202 ms	26260 KB	Output is correct
23	Correct	223 ms	26260 KB	Output is correct
24	Correct	212 ms	26260 KB	Output is correct
25	Correct	165 ms	26260 KB	Output is correct
26	Correct	200 ms	26260 KB	Output is correct
27	Correct	720 ms	33284 KB	Output is correct
28	Correct	750 ms	33284 KB	Output is correct
29	Correct	764 ms	33284 KB	Output is correct
30	Correct	715 ms	33284 KB	Output is correct
31	Correct	741 ms	33284 KB	Output is correct
32	Correct	800 ms	33284 KB	Output is correct
33	Correct	883 ms	33284 KB	Output is correct
34	Correct	741 ms	33284 KB	Output is correct
35	Correct	684 ms	33284 KB	Output is correct
36	Correct	786 ms	33284 KB	Output is correct
37	Correct	746 ms	33284 KB	Output is correct
38	Correct	1942 ms	46564 KB	Output is correct
39	Correct	1370 ms	50164 KB	Output is correct
40	Correct	1080 ms	50164 KB	Output is correct
41	Correct	2261 ms	50164 KB	Output is correct
42	Correct	747 ms	50164 KB	Output is correct
43	Correct	881 ms	50164 KB	Output is correct
44	Correct	1761 ms	50164 KB	Output is correct
45	Correct	1899 ms	50164 KB	Output is correct
46	Correct	1705 ms	50164 KB	Output is correct
47	Correct	966 ms	50164 KB	Output is correct
48	Correct	847 ms	50164 KB	Output is correct
49	Correct	1946 ms	50164 KB	Output is correct
50	Correct	1740 ms	50164 KB	Output is correct
51	Correct	2011 ms	50732 KB	Output is correct
52	Correct	900 ms	57244 KB	Output is correct
53	Correct	1315 ms	71788 KB	Output is correct
54	Correct	1556 ms	91004 KB	Output is correct
55	Correct	1196 ms	91004 KB	Output is correct

답안 #60415

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 15.0 / 15.0

Subtask #4 75.0 / 75.0

Subtask #1
5.0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
15.0 / 15.0

Subtask #4
75.0 / 75.0