oj.uz

Submission #497095

# Submission time Handle Problem Language Result Execution time Memory
497095 2021-12-22T11:26:02 Z MohamedAhmed04 Exhibition (JOI19_ho_t2) C++14
0 / 100
 0 ms 324 KB 
#include <bits/stdc++.h>

using namespace std ;

struct segtree
{
	vector<int>tree ;
	int sz ;
	void init(int sz2)
	{
		sz = sz2 + 2 ;
		tree = vector<int>(sz*4 , 0) ;
	}

	int Merge(int &x , int &y)
	{
		return max(x , y) ;
	}

	void update(int node , int l , int r , int idx , int val)
	{
		if(idx > r || idx < l)
			return ; 
		if(l == r)
		{
			tree[node] = max(tree[node] , val) ;
			return ;
		}
		int mid = (l + r) >> 1 ;
		update(node << 1 , l , mid , idx , val) ;
		update(node << 1 | 1 , mid+1 , r , idx , val) ;
		tree[node] = Merge(tree[node << 1] , tree[node << 1 | 1]) ;
	}

	int query(int node , int l , int r , int from , int to)
	{
		if(from > r || to < l)
			return 0 ;
		if(l >= from && r <= to)
			return tree[node] ;
		int mid = (l + r) >> 1 ;
		auto x = query(node << 1 , l , mid , from , to) ;
		auto y = query(node << 1 | 1 , mid+1 , r , from , to) ;
		return Merge(x , y) ;
	}

	void update(int idx , int x)
	{
		update(1 , 0 , sz , idx , x) ;
	}

	int query(int l , int r)
	{
		return query(1 , 0 , sz , l , r) ; 
	}
};

const int MAX = 1e5 + 10 ;

int arr[MAX] ;
int n , m ;

vector< pair<int , int> >vp ;

void compress()
{
	vector<int>v ;
	for(auto &p : vp)
		v.push_back(p.second) ;
	sort(v.begin() , v.end()) ;
	for(auto &p : vp)
	{
		p.second = lower_bound(v.begin() , v.end() , p.second) - v.begin() ;
		p.second++ ;
	}
}

segtree tree ;

bool check(int x)
{
	tree.init(n+2) ;
	for(auto &p : vp)
	{
		int a = tree.query(1 , p.second) ;
		int idx = x + a ;
		if(idx >= 0 && arr[idx] < p.first)
			a = -1e9 ;
		else if(idx == m-1)
			return true ;
		tree.update(p.second , a+1) ;
	}
	return false ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>m ;
	for(int i = 0 ; i < n ; ++i)
	{
		int x , y ;
		cin>>x>>y ;
		vp.emplace_back(x , y) ;
	}
	for(int i = 0 ; i < m ; ++i)
		cin>>arr[i] ;
	sort(vp.begin() , vp.end()) ;
	sort(arr , arr+m) ;
	compress() ;
	int l = 0 , r = m-1 ;
	int ans = 0 ;
	while(l <= r)
	{
		int mid = (l + r) >> 1 ;
		if(check(mid))
			ans = m-mid , r = mid-1 ;
		else
			l = mid+1 ;
	}
	return cout<<ans<<"\n" , 0 ;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Incorrect 0 ms 324 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Incorrect 0 ms 324 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Incorrect 0 ms 324 KB Output isn't correct
6 Halted 0 ms 0 KB -