oj.uz

Submission #431583

# Submission time Handle Problem Language Result Execution time Memory
431583 2021-06-17T13:16:53 Z errorgorn Long Mansion (JOI17_long_mansion) C++17
10 / 100
 3000 ms 28856 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+1,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 30 ms 16204 KB Output is correct
2 Correct 33 ms 16220 KB Output is correct
3 Correct 64 ms 16204 KB Output is correct
4 Correct 23 ms 16124 KB Output is correct
5 Correct 26 ms 16212 KB Output is correct
6 Correct 23 ms 16188 KB Output is correct
7 Correct 21 ms 16180 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16204 KB Output is correct
2 Correct 33 ms 16220 KB Output is correct
3 Correct 64 ms 16204 KB Output is correct
4 Correct 23 ms 16124 KB Output is correct
5 Correct 26 ms 16212 KB Output is correct
6 Correct 23 ms 16188 KB Output is correct
7 Correct 21 ms 16180 KB Output is correct
8 Correct 469 ms 25860 KB Output is correct
9 Correct 492 ms 25788 KB Output is correct
10 Correct 628 ms 25976 KB Output is correct
11 Correct 981 ms 26180 KB Output is correct
12 Correct 311 ms 26100 KB Output is correct
13 Correct 166 ms 26064 KB Output is correct
14 Correct 168 ms 26108 KB Output is correct
15 Correct 285 ms 26308 KB Output is correct
16 Correct 576 ms 26360 KB Output is correct
17 Correct 167 ms 26108 KB Output is correct
18 Correct 186 ms 26140 KB Output is correct
19 Correct 199 ms 26060 KB Output is correct
20 Correct 431 ms 26192 KB Output is correct
21 Correct 586 ms 26316 KB Output is correct
22 Correct 323 ms 26104 KB Output is correct
23 Correct 254 ms 25924 KB Output is correct
24 Correct 255 ms 26052 KB Output is correct
25 Correct 245 ms 25920 KB Output is correct
26 Correct 220 ms 25912 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16204 KB Output is correct
2 Correct 33 ms 16220 KB Output is correct
3 Correct 64 ms 16204 KB Output is correct
4 Correct 23 ms 16124 KB Output is correct
5 Correct 26 ms 16212 KB Output is correct
6 Correct 23 ms 16188 KB Output is correct
7 Correct 21 ms 16180 KB Output is correct
8 Correct 469 ms 25860 KB Output is correct
9 Correct 492 ms 25788 KB Output is correct
10 Correct 628 ms 25976 KB Output is correct
11 Correct 981 ms 26180 KB Output is correct
12 Correct 311 ms 26100 KB Output is correct
13 Correct 166 ms 26064 KB Output is correct
14 Correct 168 ms 26108 KB Output is correct
15 Correct 285 ms 26308 KB Output is correct
16 Correct 576 ms 26360 KB Output is correct
17 Correct 167 ms 26108 KB Output is correct
18 Correct 186 ms 26140 KB Output is correct
19 Correct 199 ms 26060 KB Output is correct
20 Correct 431 ms 26192 KB Output is correct
21 Correct 586 ms 26316 KB Output is correct
22 Correct 323 ms 26104 KB Output is correct
23 Correct 254 ms 25924 KB Output is correct
24 Correct 255 ms 26052 KB Output is correct
25 Correct 245 ms 25920 KB Output is correct
26 Correct 220 ms 25912 KB Output is correct
27 Execution timed out 3058 ms 28856 KB Time limit exceeded
28 Halted 0 ms 0 KB -