Submission #139394

#	Time	Username	Problem	Language	Result	Execution time	Memory
139394		dndhk	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	2201 ms	127324 KiB

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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75