oj.uz

Submission #133051

# Submission time Handle Problem Language Result Execution time Memory
133051 2019-07-20T06:02:30 Z eohomegrownapps Exhibition (JOI19_ho_t2) C++14
0 / 100
 2 ms 420 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 420 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Incorrect 2 ms 256 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 420 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Incorrect 2 ms 256 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 420 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Incorrect 2 ms 256 KB Output isn't correct
8 Halted 0 ms 0 KB -