oj.uz

답안 #139394

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
139394 2019-07-31T15:55:03 Z dndhk Long Mansion (JOI17_long_mansion) C++14
100 / 100
 2201 ms 127324 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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