Submission #139394

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
139394	2019-07-31T15:55:03 Z	dndhk	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	2201 ms	127324 KB

long_mansion

#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 500000;


int N, Q;
int C[MAX_N+1];
int L[MAX_N+1], R[MAX_N+1];
int L2[MAX_N+1], R2[MAX_N+1];
map<int, int> mp;
vector<int> key[MAX_N+1];


struct SEG{
	struct NODE{
		NODE(int l, int r, int mx, int mn) : l(l), r(r), mx(mx) , mn(mn){}
		int l, r;
		int mx, mn;
		// int sum, mn;
	};
	int SZ;
	vector<NODE> seg;
	void Init(int x){
		SZ = x;
		seg.pb({-1, -1, 0, INF});
		init(0, 1, SZ);
	}

	void init(int idx, int s, int e){
		if(s==e)	return;
		seg[idx].l = seg.size(); seg.pb({-1, -1, 0, INF});
		seg[idx].r = seg.size(); seg.pb({-1, -1, 0, INF});
		init(seg[idx].l, s, (s+e)/2);
		init(seg[idx].r, (s+e)/2+1, e);
	}
	void Update(int x, int y){
		update(0, 1, SZ, x, y);
	}
	void update(int idx, int s, int e, int x, int y){
		seg[idx].mx = std::max(seg[idx].mx, y);
		seg[idx].mn = std::min(seg[idx].mn, y);
		if(s==e)	return;
		if(x<=(s+e)/2){
			update(seg[idx].l, s, (s+e)/2, x, y);
		}else{
			update(seg[idx].r, (s+e)/2+1, e, x, y);
		}
	}
	int Max(int x, int y){
		return max(0, 1, SZ, x, y);
	}
	int max(int idx, int s, int e, int x, int y){
		if(x<=s && e<=y)	return seg[idx].mx;
		if(x>e || y<s)	return 0;
		return std::max(max(seg[idx].l, s, (s+e)/2, x, y), max(seg[idx].r, (s+e)/2+1, e, x, y));
	}
	int Min(int x, int y){
		return min(0, 1, SZ, x, y);
	}
	int min(int idx, int s, int e, int x, int y){
		if(x<=s && e<=y)	return seg[idx].mn;
		if(x>e || y<s)	return INF;
		return std::min(min(seg[idx].l, s, (s+e)/2, x, y), min(seg[idx].r, (s+e)/2+1, e, x, y));
	}
};

SEG Seg1, Seg2, Seg3, Seg4;
vector<pii> upd1, upd2;

void makeLR(){
	for(int i=1; i<N; i++){
		for(int j : key[i])	mp[j] = i;
		if(mp[C[i]]==0){
			L[i] = -1;
			upd1.pb({0, i});
			//Seg1.Update(i, 0);
		}else{
			L[i] = mp[C[i]];
			upd1.pb({L[i], i});
			//Seg1.Update(i, L[i]);
		}
	}
	for(int i=1; i<N; i++){	
		for(int j : key[i]){
			mp[j] = 0;
		}
	}
	for(int i=N-1; i>0; i--){
		for(int j : key[i+1])	mp[j] = i+1;
		if(mp[C[i]]==0){
			R[i] = -1;
			upd2.pb({INF, i});
			//Seg2.Update(i, N);
		}else{
			R[i] = mp[C[i]];
			upd2.pb({R[i], i});
		}
	}	
	sort(upd1.begin(), upd1.end());
	sort(upd2.begin(), upd2.end());
}

void printLR(){
	for(int i=1; i<N; i++){
		cout<<i<<" "<<L[i]<<" "<<R[i]<<endl;
	}
}

void makeLR2(){
	int idx2 = upd2.size()-1;
	for(int i=N-1; i>0; i--){
		while(idx2>0 && upd2[idx2].first>i){
			Seg2.Update(upd2[idx2].second, upd2[idx2].second);
			idx2--;
		}
		if(L[i]==-1){
			L2[i] = 0;
		}else{
			L2[i] = min(Seg2.Min(L[i], i), i);
		}
		Seg3.Update(i, L2[i]);
	}
	int idx1 = 0;
	for(int i=1; i<N; i++){
		while(idx1<upd1.size() && upd1[idx1].first<=i){
			Seg1.Update(upd1[idx1].second, upd1[idx1].second);
			idx1++;
		}
		if(R[i]==-1){
			R2[i] = INF;
		}else{
			R2[i] = 1 + max(Seg1.Max(i, R[i]-1), i);
		}
		Seg4.Update(i, R2[i]);
	}
}

void printLR2(){
	for(int i=1; i<N; i++){
		cout<<i<<" "<<L2[i]<<" "<<R2[i]<<endl;
	}
}

int main(){
	scanf("%d", &N);
	Seg1.Init(N), Seg2.Init(N);
	Seg3.Init(N), Seg4.Init(N);
	for(int i=1; i<=N-1; i++){
		scanf("%d", &C[i]);
	}
	for(int i=1; i<=N; i++){
		int x, y;
		scanf("%d", &x);
		while(x--){
			scanf("%d", &y);
			key[i].pb(y);
		}
	}
	makeLR();
	//printLR();
	makeLR2();
	//printLR2();
	scanf("%d", &Q);
	while(Q--){
		int x, y;
		scanf("%d%d", &x, &y);
		if(x<y){
			int t = Seg3.Min(x, y-1);
			if(t<x){
				printf("NO\n");
			}else{
				printf("YES\n");
			}
		}else{
			int t = Seg4.Max(y, x-1);
			if(t>x){
				printf("NO\n");
			}else{
				printf("YES\n");
			}
		}
	}
	return 0;
}

Compilation message

long_mansion.cpp: In function 'void makeLR2()':
long_mansion.cpp:146:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(idx1<upd1.size() && upd1[idx1].first<=i){
         ~~~~^~~~~~~~~~~~
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:166:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:170:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &C[i]);
   ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:174:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
long_mansion.cpp:176:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &y);
    ~~~~~^~~~~~~~~~
long_mansion.cpp:184:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
long_mansion.cpp:187:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	12536 KB	Output is correct
2	Correct	21 ms	12796 KB	Output is correct
3	Correct	24 ms	13392 KB	Output is correct
4	Correct	19 ms	12664 KB	Output is correct
5	Correct	19 ms	12536 KB	Output is correct
6	Correct	21 ms	12608 KB	Output is correct
7	Correct	20 ms	12664 KB	Output is correct

Subtask #2

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	12536 KB	Output is correct
2	Correct	21 ms	12796 KB	Output is correct
3	Correct	24 ms	13392 KB	Output is correct
4	Correct	19 ms	12664 KB	Output is correct
5	Correct	19 ms	12536 KB	Output is correct
6	Correct	21 ms	12608 KB	Output is correct
7	Correct	20 ms	12664 KB	Output is correct
8	Correct	318 ms	14952 KB	Output is correct
9	Correct	318 ms	15068 KB	Output is correct
10	Correct	328 ms	15316 KB	Output is correct
11	Correct	343 ms	15860 KB	Output is correct
12	Correct	296 ms	14976 KB	Output is correct
13	Correct	268 ms	15224 KB	Output is correct
14	Correct	270 ms	15236 KB	Output is correct
15	Correct	264 ms	15228 KB	Output is correct
16	Correct	242 ms	15480 KB	Output is correct
17	Correct	281 ms	15144 KB	Output is correct
18	Correct	282 ms	15224 KB	Output is correct
19	Correct	271 ms	15352 KB	Output is correct
20	Correct	257 ms	15436 KB	Output is correct
21	Correct	246 ms	15452 KB	Output is correct
22	Correct	289 ms	15296 KB	Output is correct
23	Correct	274 ms	15096 KB	Output is correct
24	Correct	247 ms	15264 KB	Output is correct
25	Correct	258 ms	15096 KB	Output is correct
26	Correct	260 ms	15112 KB	Output is correct

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	820 ms	35128 KB	Output is correct
2	Correct	829 ms	35296 KB	Output is correct
3	Correct	775 ms	35508 KB	Output is correct
4	Correct	930 ms	36100 KB	Output is correct
5	Correct	825 ms	35396 KB	Output is correct
6	Correct	587 ms	35664 KB	Output is correct
7	Correct	621 ms	35760 KB	Output is correct
8	Correct	635 ms	35652 KB	Output is correct
9	Correct	585 ms	35524 KB	Output is correct
10	Correct	578 ms	35232 KB	Output is correct
11	Correct	587 ms	35108 KB	Output is correct

Subtask #4

75.0 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	12536 KB	Output is correct
2	Correct	21 ms	12796 KB	Output is correct
3	Correct	24 ms	13392 KB	Output is correct
4	Correct	19 ms	12664 KB	Output is correct
5	Correct	19 ms	12536 KB	Output is correct
6	Correct	21 ms	12608 KB	Output is correct
7	Correct	20 ms	12664 KB	Output is correct
8	Correct	318 ms	14952 KB	Output is correct
9	Correct	318 ms	15068 KB	Output is correct
10	Correct	328 ms	15316 KB	Output is correct
11	Correct	343 ms	15860 KB	Output is correct
12	Correct	296 ms	14976 KB	Output is correct
13	Correct	268 ms	15224 KB	Output is correct
14	Correct	270 ms	15236 KB	Output is correct
15	Correct	264 ms	15228 KB	Output is correct
16	Correct	242 ms	15480 KB	Output is correct
17	Correct	281 ms	15144 KB	Output is correct
18	Correct	282 ms	15224 KB	Output is correct
19	Correct	271 ms	15352 KB	Output is correct
20	Correct	257 ms	15436 KB	Output is correct
21	Correct	246 ms	15452 KB	Output is correct
22	Correct	289 ms	15296 KB	Output is correct
23	Correct	274 ms	15096 KB	Output is correct
24	Correct	247 ms	15264 KB	Output is correct
25	Correct	258 ms	15096 KB	Output is correct
26	Correct	260 ms	15112 KB	Output is correct
27	Correct	820 ms	35128 KB	Output is correct
28	Correct	829 ms	35296 KB	Output is correct
29	Correct	775 ms	35508 KB	Output is correct
30	Correct	930 ms	36100 KB	Output is correct
31	Correct	825 ms	35396 KB	Output is correct
32	Correct	587 ms	35664 KB	Output is correct
33	Correct	621 ms	35760 KB	Output is correct
34	Correct	635 ms	35652 KB	Output is correct
35	Correct	585 ms	35524 KB	Output is correct
36	Correct	578 ms	35232 KB	Output is correct
37	Correct	587 ms	35108 KB	Output is correct
38	Correct	2201 ms	103416 KB	Output is correct
39	Correct	2092 ms	127324 KB	Output is correct
40	Correct	1738 ms	88228 KB	Output is correct
41	Correct	1636 ms	123604 KB	Output is correct
42	Correct	760 ms	43704 KB	Output is correct
43	Correct	729 ms	42704 KB	Output is correct
44	Correct	1351 ms	68616 KB	Output is correct
45	Correct	1311 ms	69204 KB	Output is correct
46	Correct	1302 ms	69868 KB	Output is correct
47	Correct	762 ms	43876 KB	Output is correct
48	Correct	711 ms	42180 KB	Output is correct
49	Correct	1162 ms	66364 KB	Output is correct
50	Correct	1219 ms	68112 KB	Output is correct
51	Correct	1408 ms	70900 KB	Output is correct
52	Correct	1068 ms	70820 KB	Output is correct
53	Correct	1428 ms	97628 KB	Output is correct
54	Correct	1766 ms	122916 KB	Output is correct
55	Correct	1429 ms	99972 KB	Output is correct