Submission #1320339

#TimeUsernameProblemLanguageResultExecution timeMemory
1320339Kel_MahmutExhibition (JOI19_ho_t2)C++20
0 / 100
0 ms332 KiB
#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

struct segTree{
	int n;
	vector<int> t;
	segTree(int n) : n(n), t(4 * n, INT_MAX){}

	void upd(int u, int tl, int tr, int pos, int val){
		if(tl == tr){
			t[u] = val;
			return;
		}
		int tm = (tl + tr) / 2;
		if(pos <= tm)
			upd(u * 2, tl, tm, pos, val);
		else
			upd(u * 2 + 1, tm + 1, tr, pos, val);
		t[u] = min(t[u * 2], t[u * 2 + 1]);
	}

	void upd(int pos, int val){
		upd(1, 0, n - 1, pos, val);
	}

	int walk(int u, int tl, int tr, int x){
		if(tl == tr){
			return tl;
		}
		int tm = (tl + tr) / 2;
		if(t[u * 2 + 1] <= x)
			return walk(u * 2 + 1, tm + 1, tr, x);
		return walk(u * 2, tl, tm, x);
	}

	int walk(int x){
		return walk(1, 0, n - 1, x);
	}
};

int main(){
	int n, m;
	cin >> n >> m;
	vector<array<int, 2>> a(n);
	vector<int> c(m);
	for(int i = 0; i < n; i++) cin >> a[i][1] >> a[i][0];
	for(int i = 0; i < m; i++) cin >> c[i];
	sort(all(a));
	segTree st(n);
	for(int i = 0; i < n; i++){
		st.upd(i, a[i][1]);
	}
	sort(all(c));
	int ans = 0;
	int r = n;
	for(int i = m - 1; i >= 0; i--){
		int j = st.walk(c[i]);
		if(a[j][1] > c[i]) continue;
		while(j < r){
			r--;
			st.upd(r, INT_MAX);
		}
		ans++;
	}
	cout << ans << endl;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...