Submission #777175

#	Time	Username	Problem	Language	Result	Execution time	Memory
777175		OrazB	Exhibition (JOI19_ho_t2)	C++17	0 / 100	1 ms	340 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
//Dijkstra->set
//set.find_by_order(x) x-position value
//set.order_of_key(x) number of strictly less elements don't need *set.??
#define N 300005
#define wr cout << "Continue debugging\n";
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <int, int>
#define pb push_back
#define ff first
#define ss second

int sp[N][18];

int logt(int x){
	int cur = 0;
	while(x>1){
		x /= 2;
		cur++;
	}
	return cur;
}

void build(int n, vector<int> cur){
	for (int i = 1; i <= n; i++) sp[i][0] = min(cur[i], cur[i+1]);
	for (int j = 1; j <= 17; j++){
		for (int i = 1; i <= n; i++){
			sp[i][j] = min(sp[i][j-1], sp[i+(1<<(j-1))][j-1]);
		}
	}
}
int sparse(int l, int r, vector<int> cur){
	if (l == r) return cur[l];
	int x = logt(r-l);
	return min(sp[l][x], sp[r-(1<<x)][x]);
}

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<pii> a(n+1);
	for (int i = 1; i <= n; i++) cin >> a[i].ss >> a[i].ff;
	vector<int> c(m+1);
	for (int i =1 ; i <= m; i++) cin >> c[i];
	sort(all(c)); sort(all(a));
	vector<int> cur(n+1, -1);
	for (int i = 1; i <= n; i++){
		if (c[m] < a[i].ss) continue;
		cur[i] = i+m-(lower_bound(c.begin()+1, c.end(), a[i].ss)-c.begin());
	}
	build(n, cur);
	int ans = 0;
	for (int i = 1; i <= n; i++){
		int l = i, r = n;
		while(l <= r){
			int md = (l+r)>>1;
			int x = sparse(i, md, cur);
			if (x < md) r = md - 1;
			else{
				ans = max(ans, md-i+1); 
				l = md + 1;
			} 
		}
	}
	cout << ans;
}	

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