Submission #133051

#	Time	Username	Problem	Language	Result	Execution time	Memory
133051		eohomegrownapps	Exhibition (JOI19_ho_t2)	C++14	0 / 100	2 ms	420 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> frames;
vector<pair<ll,ll> > pictures;
vector<ll> fenwick;
ll fsize;
void update(ll x){
	//cout<<x<<endl;
	while (x<=fsize){
		fenwick[x]++;
		x+=x&(-x);
	}
}

ll get(ll x){
	ll ans = 0;
	while (x>0){
		ans+=fenwick[x];
		x-=x&(-x);
	}
	return ans;
}

int main(){
	//freopen("exhibition.in","r",stdin);
	ll n,m;
	cin>>n>>m;
	frames.resize(m);
	pictures.resize(n);
	for (int i = 0; i<n; i++){
		cin>>pictures[i].second>>pictures[i].first;
	}
	sort(pictures.begin(),pictures.end());
	for (int i = 0; i<m; i++){
		cin>>frames[i];
	}
	sort(frames.begin(),frames.end());
	fenwick.resize(n+m+2,0);
	fsize=n+m+1;
	ll ans = 0;
	int picindex = 0;
	for (int i = n; i>=1; i--){
		//end position at i+m-1
		//find first frame >= pictures[picindex].second
		auto it = lower_bound(frames.begin(),frames.end(),pictures[picindex].second);
		if (it!=frames.end()){
			int offset = it-frames.begin();
			update(i+offset+1);
		} 
		ans=max(ans,get(i+m));
		picindex++;
		/*for (int i = 1; i<=n+m+1; i++){
			cout<<get(i)<<" ";
		}cout<<endl;*/
	}
	cout<<ans<<endl;
	return 0;
}

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