Submission #961629

#	Time	Username	Problem	Language	Result	Execution time	Memory
961629		starchan	Matryoshka (JOI16_matryoshka)	C++17	100 / 100	299 ms	21572 KiB

matryoshka

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17

#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 2e5+5;

vector<int> G;
vector<int> H;
signed main()
{
	fast();
	int n, q;
	cin >> n >> q;
	vector<pair<in, int>> Q(q);
	vector<in> RH(n+1);
	RH[0] = {-INF, -1};
	for(int i = 1; i <= n; i++)
	{
		cin >> RH[i].f >> RH[i].s;
		RH[i].f = -RH[i].f;
		G.pb(RH[i].f);
	}
	for(int i = 0; i < q; i++)
	{
		Q[i].s = i;
		cin >> Q[i].f.f >> Q[i].f.s;
		Q[i].f.f = -Q[i].f.f;
		G.pb(Q[i].f.f);
	}
	sort(RH.begin(), RH.end());
	sort(G.begin(), G.end());
	H.pb(G[0]);
	for(auto x: G)
	{
		if(x != H.back())
			H.pb(x);
	}
	G.clear();
	for(auto &[u, v]: RH)
	{
		u = lower_bound(H.begin(), H.end(), u)-H.begin()+1;
		G.pb(v);
	}
	for(auto &[qq, i]: Q)
	{
		qq.f = lower_bound(H.begin(), H.end(), qq.f)-H.begin()+1;
		G.pb(qq.s);
	}
	H.clear();
	sort(G.begin(), G.end());
	H.pb(G[0]);
	for(auto x: G)
	{
		if(x != H.back())
			H.pb(x);
	}
	for(auto &[u, v]: RH)
		v = lower_bound(H.begin(), H.end(), v)-H.begin()+1;
	for(auto &[qq, i]: Q)
		qq.s = lower_bound(H.begin(), H.end(), qq.s)-H.begin()+1;
	sort(Q.begin(), Q.end());
	/*cout << "Printing RH values" << endl;
	for(auto [u, v]: RH)
		cout << u << " " << v << endl;*/
	int r = 1;
	vector<int> ans(q, 0);
	vector<in> d(n+1, {INF, INF});
	d[0] = {-INF, -INF};
	for(int i = 0; i < q; i++)
	{
		int x = Q[i].s;
		while((r <= n) && (RH[r].f <= Q[i].f.f))
		{
			//add RH[r].s
			//RH[r].s can provide
			in pp = {RH[r].s, r}; 
			int W = upper_bound(d.begin(), d.end(), pp) - d.begin();
			if((d[W-1] < pp) && (pp < d[W]))
				d[W] = pp;
			r++;
		}
		in ok = {Q[i].f.s, INF};
		ans[x] = upper_bound(d.begin(), d.end(), ok)-d.begin()-1;
	}
	for(int i = 0; i < q; i++)
		cout << ans[i] << "\n";
	return 0;
}	

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 49 / 49