oj.uz

Submission #431580

# Submission time Handle Problem Language Result Execution time Memory
431580 2021-06-17T13:16:08 Z errorgorn Long Mansion (JOI17_long_mansion) C++17
10 / 100
 3000 ms 28868 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,q;
int arr[500005];
vector<int> keys[500005];
ii queries[500005];
bool ans[500005];

int lpos[500005];
int rpos[500005];
int has[500005];

int bad[500005];

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n;
	rep(x,1,n) cin>>arr[x];
	
	int a,b;
	rep(x,1,n+1){
		cin>>a;
		rep(y,0,a){
			cin>>b;
			keys[x].pub(b);
		}
	}
	
	cin>>q;
	rep(x,0,q) cin>>queries[x].fi>>queries[x].se;
	
	rep(zzz,0,2){ //change to 2 later
		rep(x,0,500005) has[x]=1e9;
		rep(x,n,1){
			for (auto &it:keys[x+1]) has[it]=x+1;
			lpos[x]=has[arr[x]];
		}
		
		rep(x,0,500005) has[x]=-1e9;
		rep(x,1,n){
			for (auto &it:keys[x]) has[it]=x;
			rpos[x+1]=has[arr[x]];
		}
		
		//rep(x,1,n+1) cout<<lpos[x]<<" "; cout<<endl;
		//rep(x,1,n+1) cout<<rpos[x]<<" "; cout<<endl;
		
		memset(bad,-1,sizeof(bad));
		rep(x,1,n){
			rep(y,x+2,n+1){
				if (lpos[x]>=y && x>=rpos[y]) bad[x]=y;
			}
			if (lpos[x]==1e9) bad[x]=1e9;
		}
		
		//rep(x,1,n+1) cout<<bad[x]<<" "; cout<<endl<<endl;
		
		rep(x,0,q) if (queries[x].se<queries[x].fi){
			//cout<<"query: "<<x<<endl;
			
			bool can=true;
			rep(y,queries[x].se,queries[x].fi){
				//cout<<y<<" "<<bad[y]<<endl;
				if (queries[x].fi<bad[y]) can=false;
			}
			
			ans[x]=can;
		}
		
		//flip shit now
		reverse(arr+1,arr+n);
		reverse(keys+1,keys+n+1);
		rep(x,0,q) tie(queries[x].fi,queries[x].se)=ii(n-queries[x].fi+1,n-queries[x].se+1);
	}
	
	rep(x,0,q){
		if (ans[x]) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16176 KB Output is correct
2 Correct 31 ms 16220 KB Output is correct
3 Correct 59 ms 16312 KB Output is correct
4 Correct 20 ms 16180 KB Output is correct
5 Correct 25 ms 16100 KB Output is correct
6 Correct 20 ms 16204 KB Output is correct
7 Correct 21 ms 16184 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16176 KB Output is correct
2 Correct 31 ms 16220 KB Output is correct
3 Correct 59 ms 16312 KB Output is correct
4 Correct 20 ms 16180 KB Output is correct
5 Correct 25 ms 16100 KB Output is correct
6 Correct 20 ms 16204 KB Output is correct
7 Correct 21 ms 16184 KB Output is correct
8 Correct 493 ms 25920 KB Output is correct
9 Correct 492 ms 25796 KB Output is correct
10 Correct 715 ms 26036 KB Output is correct
11 Correct 1020 ms 26196 KB Output is correct
12 Correct 350 ms 26004 KB Output is correct
13 Correct 176 ms 26096 KB Output is correct
14 Correct 233 ms 26108 KB Output is correct
15 Correct 295 ms 26100 KB Output is correct
16 Correct 614 ms 26396 KB Output is correct
17 Correct 172 ms 26072 KB Output is correct
18 Correct 187 ms 26032 KB Output is correct
19 Correct 225 ms 26076 KB Output is correct
20 Correct 467 ms 26304 KB Output is correct
21 Correct 607 ms 26300 KB Output is correct
22 Correct 330 ms 26096 KB Output is correct
23 Correct 247 ms 25920 KB Output is correct
24 Correct 241 ms 25924 KB Output is correct
25 Correct 247 ms 25908 KB Output is correct
26 Correct 209 ms 25916 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16176 KB Output is correct
2 Correct 31 ms 16220 KB Output is correct
3 Correct 59 ms 16312 KB Output is correct
4 Correct 20 ms 16180 KB Output is correct
5 Correct 25 ms 16100 KB Output is correct
6 Correct 20 ms 16204 KB Output is correct
7 Correct 21 ms 16184 KB Output is correct
8 Correct 493 ms 25920 KB Output is correct
9 Correct 492 ms 25796 KB Output is correct
10 Correct 715 ms 26036 KB Output is correct
11 Correct 1020 ms 26196 KB Output is correct
12 Correct 350 ms 26004 KB Output is correct
13 Correct 176 ms 26096 KB Output is correct
14 Correct 233 ms 26108 KB Output is correct
15 Correct 295 ms 26100 KB Output is correct
16 Correct 614 ms 26396 KB Output is correct
17 Correct 172 ms 26072 KB Output is correct
18 Correct 187 ms 26032 KB Output is correct
19 Correct 225 ms 26076 KB Output is correct
20 Correct 467 ms 26304 KB Output is correct
21 Correct 607 ms 26300 KB Output is correct
22 Correct 330 ms 26096 KB Output is correct
23 Correct 247 ms 25920 KB Output is correct
24 Correct 241 ms 25924 KB Output is correct
25 Correct 247 ms 25908 KB Output is correct
26 Correct 209 ms 25916 KB Output is correct
27 Execution timed out 3044 ms 28868 KB Time limit exceeded
28 Halted 0 ms 0 KB -