Submission #883166

#	Time	Username	Problem	Language	Result	Execution time	Memory
883166		NotLinux	Exhibition (JOI19_ho_t2)	C++17	100 / 100	934 ms	20652 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 7;//wrong yerse N i değiştirmeyi unutma
const int inf = 1e9 + 7;
struct SEGT{
	vector < int > tree;
	int sz;
	SEGT(int x){
		sz = x+3;
		tree.assign(4*sz , inf);
	}
	int _query(int ind , int l , int r , int ql , int qr){
		if(l >= ql and r <= qr)return tree[ind];
		else if(l > qr or r < ql)return inf;
		int mid = (l+r)/2;
		return min(_query(ind*2,l,mid,ql,qr) , _query(ind*2+1,mid+1,r,ql,qr));
	}
	int query(int l , int r){
		return _query(1,1,sz,l,r);
	}
	void _update(int ind , int l , int r , int qp , int qv){
		if(l == r){
			tree[ind] = qv;
			return;
		}
		int mid = (l+r)/2;
		if(mid >= qp)_update(ind*2,l,mid,qp,qv);
		else _update(ind*2+1,mid+1,r,qp,qv);
		tree[ind] = min(tree[ind*2] , tree[ind*2+1]);
	}
	void update(int p , int v){
		_update(1,1,sz,p,v);
	}
};
int n , m , frame[N];
pair < int , int > picture[N];
vector < int > comp;
bool check(int x){
	SEGT segt(N);
	vector < int > ind[N];
	for(int i = 0;i<n;i++){
		ind[picture[i].second].push_back(i);
	}
	for(int i = 0;i<N;i++){
		if(ind[i].size()){
			sort(ind[i].begin() , ind[i].end());
			reverse(ind[i].begin() , ind[i].end());
			segt.update(i,ind[i].back());
		}
	}
	int last = 0;
	for(int i = m-x;i<m;i++){
		int nxt = segt.query(1,frame[i]);
		if(nxt == inf)return 0;
		while(last <= nxt){
			ind[picture[last].second].pop_back();
			if(ind[picture[last].second].size()){
				segt.update(picture[last].second , ind[picture[last].second].back());
			}
			else{
				segt.update(picture[last].second , inf);
			}
			last++;
		}
	}
	return 1;
}
void solve(){
	cin >> n >> m;
	for(int i = 0;i<n;i++){
		cin >> picture[i].second >> picture[i].first;
		comp.push_back(picture[i].second);
	}
	for(int i = 0;i<m;i++){
		cin >> frame[i];
		comp.push_back(frame[i]);
	}
	sort(comp.begin() , comp.end());
	comp.resize(unique(comp.begin() , comp.end()) - comp.begin());
	for(int i = 0;i<n;i++){
		picture[i].second = lower_bound(comp.begin() , comp.end() , picture[i].second) - comp.begin() + 1;
	}
	for(int i = 0;i<m;i++){
		frame[i] = lower_bound(comp.begin() , comp.end() , frame[i]) - comp.begin() + 1;
	}

	sort(frame , frame + m);
	sort(picture , picture + n);
	int l = 0 , r = n+1 , ans = 0;
	while(l < r){
		int mid = (l+r)/2;
		if(check(mid)){
			ans = mid;
			l = mid+1;
		}
		else r = mid;
	}
	cout << ans << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50