oj.uz

Submission #564364

# Submission time Handle Problem Language Result Execution time Memory
564364 2022-05-19T04:08:24 Z amunduzbaev Long Mansion (JOI17_long_mansion) C++17
10 / 100
 3000 ms 26608 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array

const int N = 5e5 + 5;

struct ST{
	ar<int, 2> tree[N << 2];
	void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = {v, v}; return; }
		int m = (lx + rx) >> 1;
		if(i <= m) sett(i, v, lx, m, x<<1);
		else sett(i, v, m+1, rx, x<<1|1);
		tree[x][0] = min(tree[x<<1][0], tree[x<<1|1][0]);
		tree[x][1] = max(tree[x<<1][1], tree[x<<1|1][1]);
	}
	
	//~ int Max(int l, int r, int lx = 0, int rx = N, int x = 1){
		//~ if(lx > r || rx < l) return -N;
		//~ if(lx >= l && rx <= r) return tree[x][1];
		//~ int m = (lx + rx) >> 1;
		//~ return max(Max(l, r, lx, m, x<<1), Max(l, r, m+1, rx, x<<1|1));
	//~ }
	
	int Min(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return N;
		if(lx >= l && rx <= r) return tree[x][0];
		int m = (lx + rx) >> 1;
		return min(Min(l, r, lx, m, x<<1), Min(l, r, m+1, rx, x<<1|1));
	}
	
	int get(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -1;
		if(lx >= l && rx <= r){
			if(v > tree[x][1]) return -1;
			if(lx == rx) return lx;
			int m = (lx + rx) >> 1;
			if(tree[x<<1][1] >= v) return get(l, r, v, lx, m, x<<1);
			else return get(l, r, v, m+1, rx, x<<1|1);
		} int m = (lx + rx) >> 1;
		int R = get(l, r, v, lx, m, x<<1);
		if(~R) return R;
		return get(l, r, v, m+1, rx, x<<1|1);
	}
}tree;

vector<int> a[N];
int b[N], c[N], x[N], y[N];
int q, n, is[N], lp[N], rp[N];
int last[N], val[N];
int tmp[N];

void solve(){
	memset(last, 0, sizeof last);
	for(int i=1;i<n;i++){
		for(auto x : a[i]){
			last[x] = i;
		}
		
		lp[i] = last[c[i]];
	}
	
	//~ for(int i=1;i<n;i++) cout<<c[i]<<" ";
	//~ cout<<"\n";
	//~ for(int i=1;i<=n;i++){
		//~ for(auto x : a[i]) cout<<x<<" ";
		//~ cout<<"\n";
	//~ }
	
	memset(last, 0, sizeof last);
	for(int i=n-1;i>0;i--){
		for(auto x : a[i+1]){
			last[x] = i + 1;
		}
		rp[i] = last[c[i]];
		//~ tree.sett(i, rp[i]);
	}
	//~ for(int i=1;i<n;i++) cout<<lp[i]<<" ";
	//~ cout<<"\n";
	
	//~ for(int i=1;i<n;i++){
		//~ if(lp[i]){
			//~ if(lp[i] < i){
				//~ val[i] = tree.get(lp[i], i - 1, i + 1);
				//~ if(val[i] < 0) val[i] = N;
			//~ } else val[i] = N;
		//~ } else {
			//~ val[i] = -1;
		//~ }
	//~ }
	//~ for(int i=1;i<n;i++){
		//~ tree.sett(i, val[i]);
	//~ }
	
	for(int i=0;i<q;i++){
		if(x[i] > y[i]){
			continue;
		}
		
		//~ y[i]--;
		//~ is[i] |= (tree.Min(x[i], y[i]) >= x[i]);
		//~ y[i]++;
		int mx = -1;
		for(int j=x[i]-1;j>0;j--){
			if(!rp[j]) mx = N;
			mx = max(mx, rp[j]);
			tmp[j] = mx;
		}
		bool ok = 1;
		for(int j=x[i];j<y[i];j++){
			if(!lp[j]) ok = 0;
			if(lp[j] < x[i] && j < tmp[lp[j]]){
				ok = 0;
			}
		}
		
		is[i] |= ok;
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>c[i];
	}
	
	for(int i=1;i<=n;i++){
		cin>>b[i];
		a[i].resize(b[i]);
		for(int j=0;j<b[i];j++){
			cin>>a[i][j];
		}
	}
	
	cin>>q;
	for(int i=0;i<q;i++){
		cin>>x[i]>>y[i];
	}
	
	solve();
	for(int i=1;i<n-i;i++){
		swap(c[i], c[n-i]);
	}
	
	for(int i=1;i<n-i+1;i++){
		swap(b[i], b[n-i+1]);
		swap(a[i], a[n-i+1]);
	}
	
	for(int i=0;i<q;i++){
		x[i] = n - x[i] + 1;
		y[i] = n - y[i] + 1;
	}
	
	solve();
	for(int i=0;i<q;i++){
		if(is[i]) cout<<"YES\n";
		else cout<<"NO\n";
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14180 KB Output is correct
2 Correct 20 ms 14244 KB Output is correct
3 Correct 28 ms 14404 KB Output is correct
4 Correct 17 ms 14236 KB Output is correct
5 Correct 22 ms 14308 KB Output is correct
6 Correct 16 ms 14328 KB Output is correct
7 Correct 17 ms 14328 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14180 KB Output is correct
2 Correct 20 ms 14244 KB Output is correct
3 Correct 28 ms 14404 KB Output is correct
4 Correct 17 ms 14236 KB Output is correct
5 Correct 22 ms 14308 KB Output is correct
6 Correct 16 ms 14328 KB Output is correct
7 Correct 17 ms 14328 KB Output is correct
8 Correct 851 ms 25904 KB Output is correct
9 Correct 905 ms 25808 KB Output is correct
10 Correct 1196 ms 26308 KB Output is correct
11 Correct 1941 ms 26608 KB Output is correct
12 Correct 500 ms 25548 KB Output is correct
13 Correct 877 ms 26056 KB Output is correct
14 Correct 855 ms 26064 KB Output is correct
15 Correct 970 ms 26060 KB Output is correct
16 Correct 1166 ms 25848 KB Output is correct
17 Correct 822 ms 26124 KB Output is correct
18 Correct 817 ms 26092 KB Output is correct
19 Correct 826 ms 26100 KB Output is correct
20 Correct 1085 ms 26060 KB Output is correct
21 Correct 1295 ms 25988 KB Output is correct
22 Correct 967 ms 25992 KB Output is correct
23 Correct 966 ms 25844 KB Output is correct
24 Correct 955 ms 25852 KB Output is correct
25 Correct 961 ms 25808 KB Output is correct
26 Correct 893 ms 25892 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3090 ms 23508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14180 KB Output is correct
2 Correct 20 ms 14244 KB Output is correct
3 Correct 28 ms 14404 KB Output is correct
4 Correct 17 ms 14236 KB Output is correct
5 Correct 22 ms 14308 KB Output is correct
6 Correct 16 ms 14328 KB Output is correct
7 Correct 17 ms 14328 KB Output is correct
8 Correct 851 ms 25904 KB Output is correct
9 Correct 905 ms 25808 KB Output is correct
10 Correct 1196 ms 26308 KB Output is correct
11 Correct 1941 ms 26608 KB Output is correct
12 Correct 500 ms 25548 KB Output is correct
13 Correct 877 ms 26056 KB Output is correct
14 Correct 855 ms 26064 KB Output is correct
15 Correct 970 ms 26060 KB Output is correct
16 Correct 1166 ms 25848 KB Output is correct
17 Correct 822 ms 26124 KB Output is correct
18 Correct 817 ms 26092 KB Output is correct
19 Correct 826 ms 26100 KB Output is correct
20 Correct 1085 ms 26060 KB Output is correct
21 Correct 1295 ms 25988 KB Output is correct
22 Correct 967 ms 25992 KB Output is correct
23 Correct 966 ms 25844 KB Output is correct
24 Correct 955 ms 25852 KB Output is correct
25 Correct 961 ms 25808 KB Output is correct
26 Correct 893 ms 25892 KB Output is correct
27 Execution timed out 3090 ms 23508 KB Time limit exceeded
28 Halted 0 ms 0 KB -