Submission #494728

#	Time	Username	Problem	Language	Result	Execution time	Memory
494728		Haruto810198	Exhibition (JOI19_ho_t2)	C++17	0 / 100	2 ms	1868 KiB

joi2019_ho_t2

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

#define lsb(x) ((x)&(-(x)))

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 100010;

int n, m;
pii pic[MAX]; // val, sz
int frame[MAX]; // sz
int res;

int dp[MAX];
int BIT[2*MAX];

void init(){
	FOR(i, 1, 2*MAX-1, 1){
		BIT[i] = 0;
	}
}

void modify(int pos, int val){
	while(pos < 2*MAX){
		BIT[pos] = max(BIT[pos], val);
		pos += lsb(pos);
	}
}

int query(int pos){
	int ret = 0;
	while(pos > 0){
		ret = max(ret, BIT[pos]);
		pos -= lsb(pos);
	}
	return ret;
}

bool check(int frames){
	
	if(frames == 0) return 1;
	
	bool ret = 0;

	// init
	init();
	
	// dp
	FOR(i, 1, n, 1){
		dp[i] = query(pic[i].S) + 1;
		
		if(frame[m - frames + dp[i]] < pic[i].S) continue;
		
		modify(pic[i].S, dp[i]);
		if(dp[i] >= frames) ret = 1;
	}
	
	return ret;

}

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m;
	FOR(i, 1, n, 1){
		cin>>pic[i].S>>pic[i].F;
	}
	FOR(i, 1, m, 1){
		cin>>frame[i];
	}
	
	sort(pic+1, pic+n+1);
	sort(frame+1, frame+m+1);
	
	// -> [1, n+m]
	map<int, int> mp;
	vi tmp;

	FOR(i, 1, n, 1){
		tmp.pb(pic[i].S);
	}
	FOR(i, 1, m, 1){
		tmp.pb(frame[i]);
	}
	
	sort(tmp.begin(), tmp.end());

	for(int i : tmp){
		if(mp.find(i) == mp.end()) mp[i] = szof(mp) + 1;
	}
	
	FOR(i, 1, n, 1){
		pic[i].S = mp[pic[i].S];
	}
	FOR(i, 1, m, 1){
		frame[i] = mp[frame[i]];
	}
	
	FOR(i, 0, m-1, 1){
		assert(check(i) >= check(i+1));
	}

	// bs for res
	int L = 0, R = m, mid;
	while(L < R){
		mid = (L + R + 1) / 2;
		if(check(mid)) L = mid;
		else R = mid - 1;
	}

	cout<<L<<'\n';

	return 0;

}

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