oj.uz

Submission #431615

# Submission time Handle Problem Language Result Execution time Memory
431615 2021-06-17T13:38:39 Z errorgorn Long Mansion (JOI17_long_mansion) C++17
100 / 100
 1666 ms 96864 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());

struct node{
	int s,e,m;
	int val;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void update(int i,int k){
		if (s==e) val=max(val,k);
		else{
			if (i<=m) l->update(i,k);
			else if (m<i) r->update(i,k);
			
			val=max(l->val,r->val);
		}
	}
	
	int query(int i,int j){
		if (s==i && e==j) return val;
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return max(l->query(i,m),r->query(m+1,j));
	}
	
	void clear(){
		val=0;
		if (s!=e) l->clear(),r->clear();
	}
} *root=new node(0,500005);

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]=0;
		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;
		
		//maximize y
		//lpos[x]>=y, so we add into segtree add in increasing y
		//segtree needs x>=rpos[y], so add rpos[y] into segtree
		//then we query maximum
		
		memset(bad,-1,sizeof(bad));
		root->clear();
		
		vector<int> proc;
		rep(x,1,n) proc.pub(x);
		sort(all(proc),[](int i,int j){
			return lpos[i]<lpos[j];
		});
		
		int curr=2;
		for (auto &it:proc){
			while (curr<=n && curr<=lpos[it]){
				root->update(rpos[curr],curr);
				curr++;
			}
			
			bad[it]=root->query(0,it);
			if (lpos[it]==1e9) bad[it]=1e9;
		}
		
		//rep(x,1,n+1) cout<<bad[x]<<" "; cout<<endl<<endl;
		
		root->clear();
		rep(x,1,n) root->update(x,bad[x]);
		
		rep(x,0,q) if (queries[x].se<queries[x].fi){
			//cout<<"query: "<<x<<endl;
			
			ans[x]=queries[x].fi>=root->query(queries[x].se,queries[x].fi-1);
		}
		
		//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;
	}
}

Compilation message

long_mansion.cpp: In constructor 'node::node(int, int)':
long_mansion.cpp:29:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 63148 KB Output is correct
2 Correct 94 ms 63144 KB Output is correct
3 Correct 114 ms 63308 KB Output is correct
4 Correct 101 ms 63144 KB Output is correct
5 Correct 86 ms 63172 KB Output is correct
6 Correct 89 ms 63124 KB Output is correct
7 Correct 111 ms 63064 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 63148 KB Output is correct
2 Correct 94 ms 63144 KB Output is correct
3 Correct 114 ms 63308 KB Output is correct
4 Correct 101 ms 63144 KB Output is correct
5 Correct 86 ms 63172 KB Output is correct
6 Correct 89 ms 63124 KB Output is correct
7 Correct 111 ms 63064 KB Output is correct
8 Correct 330 ms 72812 KB Output is correct
9 Correct 355 ms 72868 KB Output is correct
10 Correct 353 ms 73008 KB Output is correct
11 Correct 358 ms 73272 KB Output is correct
12 Correct 317 ms 73028 KB Output is correct
13 Correct 303 ms 73064 KB Output is correct
14 Correct 299 ms 73028 KB Output is correct
15 Correct 323 ms 73104 KB Output is correct
16 Correct 317 ms 73272 KB Output is correct
17 Correct 283 ms 73000 KB Output is correct
18 Correct 291 ms 73072 KB Output is correct
19 Correct 316 ms 73064 KB Output is correct
20 Correct 285 ms 73180 KB Output is correct
21 Correct 317 ms 73352 KB Output is correct
22 Correct 287 ms 73028 KB Output is correct
23 Correct 295 ms 72964 KB Output is correct
24 Correct 287 ms 72912 KB Output is correct
25 Correct 321 ms 72884 KB Output is correct
26 Correct 284 ms 72904 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 849 ms 77988 KB Output is correct
2 Correct 741 ms 77992 KB Output is correct
3 Correct 833 ms 77896 KB Output is correct
4 Correct 884 ms 77928 KB Output is correct
5 Correct 854 ms 77992 KB Output is correct
6 Correct 637 ms 77484 KB Output is correct
7 Correct 636 ms 77636 KB Output is correct
8 Correct 608 ms 77660 KB Output is correct
9 Correct 582 ms 77680 KB Output is correct
10 Correct 578 ms 77652 KB Output is correct
11 Correct 621 ms 77620 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 63148 KB Output is correct
2 Correct 94 ms 63144 KB Output is correct
3 Correct 114 ms 63308 KB Output is correct
4 Correct 101 ms 63144 KB Output is correct
5 Correct 86 ms 63172 KB Output is correct
6 Correct 89 ms 63124 KB Output is correct
7 Correct 111 ms 63064 KB Output is correct
8 Correct 330 ms 72812 KB Output is correct
9 Correct 355 ms 72868 KB Output is correct
10 Correct 353 ms 73008 KB Output is correct
11 Correct 358 ms 73272 KB Output is correct
12 Correct 317 ms 73028 KB Output is correct
13 Correct 303 ms 73064 KB Output is correct
14 Correct 299 ms 73028 KB Output is correct
15 Correct 323 ms 73104 KB Output is correct
16 Correct 317 ms 73272 KB Output is correct
17 Correct 283 ms 73000 KB Output is correct
18 Correct 291 ms 73072 KB Output is correct
19 Correct 316 ms 73064 KB Output is correct
20 Correct 285 ms 73180 KB Output is correct
21 Correct 317 ms 73352 KB Output is correct
22 Correct 287 ms 73028 KB Output is correct
23 Correct 295 ms 72964 KB Output is correct
24 Correct 287 ms 72912 KB Output is correct
25 Correct 321 ms 72884 KB Output is correct
26 Correct 284 ms 72904 KB Output is correct
27 Correct 849 ms 77988 KB Output is correct
28 Correct 741 ms 77992 KB Output is correct
29 Correct 833 ms 77896 KB Output is correct
30 Correct 884 ms 77928 KB Output is correct
31 Correct 854 ms 77992 KB Output is correct
32 Correct 637 ms 77484 KB Output is correct
33 Correct 636 ms 77636 KB Output is correct
34 Correct 608 ms 77660 KB Output is correct
35 Correct 582 ms 77680 KB Output is correct
36 Correct 578 ms 77652 KB Output is correct
37 Correct 621 ms 77620 KB Output is correct
38 Correct 1633 ms 92100 KB Output is correct
39 Correct 1666 ms 96776 KB Output is correct
40 Correct 1365 ms 87412 KB Output is correct
41 Correct 1568 ms 96864 KB Output is correct
42 Correct 539 ms 77388 KB Output is correct
43 Correct 522 ms 77336 KB Output is correct
44 Correct 754 ms 81668 KB Output is correct
45 Correct 718 ms 81880 KB Output is correct
46 Correct 742 ms 81684 KB Output is correct
47 Correct 557 ms 77548 KB Output is correct
48 Correct 610 ms 77464 KB Output is correct
49 Correct 740 ms 81684 KB Output is correct
50 Correct 757 ms 81724 KB Output is correct
51 Correct 777 ms 81684 KB Output is correct
52 Correct 780 ms 81684 KB Output is correct
53 Correct 952 ms 87520 KB Output is correct
54 Correct 1135 ms 92080 KB Output is correct
55 Correct 954 ms 87360 KB Output is correct