Submission #1272454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272454		namhh	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	164 ms	7584 KiB

matryoshka

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e5+5;
int n,q,bits[N],ans[N];
pii a[N];
vector<int>v;
struct emilia{
	int id,x,y;
};
emilia qr[N];
bool cmp(pii a, pii b){
	if(a.fi == b.fi) return a.se > b.se;
	return a.fi < b.fi;
}
bool cmp1(emilia a, emilia b){
	return a.x > b.x;
}
void update(int u, int val){
	while(u <= v.size()){
		bits[u] = max(bits[u],val);
		u += u & (-u);
	}
}
int get(int u){
	int res = 0;
	while(u > 0){
		res = max(res,bits[u]);
	    u -= u & (-u);
	}
	return res;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		cin >> a[i].fi >> a[i].se;
		v.push_back(a[i].se);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	sort(a+1,a+n+1,cmp);
	for(int i = 1; i <= n; i++) a[i].se = lower_bound(v.begin(),v.end(),a[i].se)-v.begin()+1;
	for(int i = 1; i <= q; i++){
		cin >> qr[i].x >> qr[i].y;
		qr[i].id = i;
		qr[i].y = upper_bound(v.begin(),v.end(),qr[i].y)-v.begin();
	}
	sort(qr+1,qr+q+1,cmp1);
	int cur = n;
	for(int i = 1; i <= q; i++){
		auto[id,x,y] = qr[i];
		while(cur >= 1 && a[cur].fi >= x){
			int rem = get(a[cur].se)+1;
			update(a[cur].se,rem);
			cur--;
		}
		ans[id] = get(y);
	}
	for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

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