Submission #1273461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273461		g4yuhg	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	122 ms	14320 KiB

matryoshka

#include<bits/stdc++.h>
typedef long long ll;
#define int long long
#define endl '\n'
#define fi first
#define se second
#define pii pair<ll, ll>
#define N 500005
using namespace std;

bool ghuy4g;

const ll inf = 2e9;

ll n, q, kq[N];

pii a[N];

struct QR {
	ll A, B, id;
} qr[N];

bool cmp(QR a, QR b) {
	return a.A > b.A;
}

// tim so day tang nghiem ngat nho nhat de bao phu 
// => do chinh la so phan tu cua day khong tang dai nhat LNIS

void solve() {
	sort(a + 1, a + 1 + n, greater<pii>());
	sort(qr + 1, qr + 1 + q, cmp);
	ll cur = 1;
	vector<pii> dp;
	for (int i = 1; i <= q; i ++) {
		while (cur <= n && a[cur].fi >= qr[i].A) {
			ll it = upper_bound(dp.begin(), dp.end(), make_pair(-a[cur].se, inf)) - dp.begin();
			if (it == dp.size()) {
				dp.push_back({-a[cur].se, a[cur].fi});
			}
			else {
				dp[it] = {-a[cur].se, a[cur].fi};
			}
			cur ++ ;
		}
		kq[qr[i].id] = upper_bound(dp.begin(), dp.end(), make_pair(qr[i].B, inf)) - dp.begin();
	}
	for (int i = 1; i <= q; i ++) {
		cout << kq[i] << endl;
	}
}

bool klinh;

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cout.tie(0);
	
	cin >> n >> q;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i].fi >> a[i].se;
		a[i].se = -a[i].se; // de sort, ko tinh trung cac con chung first
	}
	
	for (int i = 1; i <= q; i ++) {
		cin >> qr[i].A >> qr[i].B;
		qr[i].id = i;
	}
	
	solve();
	
	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024); 
	
	return 0;
}

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