제출 #1288601

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288601		vuviet	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	342 ms	63088 KiB

matryoshka

/**
 *  __      __   __      __
 *  \ \    / /   \ \    / (_)     _____
 *   \ \  / /_   _\ \  / / _  ___|_   _|
 *    \ \/ /| | | |\ \/ / | |/ _ \ | |
 *     \  / | |_| | \  /  | |  __/ | |
 *      \/   \__,_|  \/   |_|\____||_|
 *
 *     Author:    ~Noah's Ark~
 *     Born on:   2024-24-03 11:15
**/

#include <iostream>
#include <vector>
#include <algorithm>
#define ____vuviet__ signed main
#define taskname "matryoshka"

using namespace std;
using lli = long long;

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define bs binary_search
#define lb lower_bound
#define ub upper_bound

#define GetBit(x, k) ((x >> k) & 1)
#define OnBit(x, k) (x | (1LL << k))
#define OffBit(x, k) (x & ~(1LL << k))
#define FlipBit(x, k) (x ^ (1LL << k))

constexpr int maxn = 1e6 + 36;
vector<int> grp[maxn], question[maxn];
int n, q, r[maxn], h[maxn];
pair<int, int> qr[maxn];

struct TFenwickTree
{
	vector<lli> data;
	int sz;
	void init(int sz)
	{
		this->sz = sz;
		data.resize(sz + 1);
	}
	void update(int i, lli v)
	{
		for (; i <= sz; i += (i & -i))
			data[i] = max(data[i], v);
	}
	lli get(int i)
	{
		lli res = 0;
		for (; i > 0; i -= (i & -i))
			res = max(res, data[i]);
		return res;
	}
};

void Initial()
{
	vector<int> vals;
	for (int i = 1; i <= n; ++i)
		vals.pb(r[i]), vals.pb(h[i]);
	for (int i = 1; i <= q; ++i)
		vals.pb(qr[i].fi), vals.pb(qr[i].se);
	sort(all(vals));
	vals.resize(unique(all(vals)) - vals.begin());
	for (int i = 1; i <= n; ++i)
	{
		r[i] = lb(all(vals), r[i]) - vals.begin() + 1;
		h[i] = lb(all(vals), h[i]) - vals.begin() + 1;
	}
	for (int i = 1; i <= q; ++i)
	{
		qr[i].fi = lb(all(vals), qr[i].fi) - vals.begin() + 1;
		qr[i].se = lb(all(vals), qr[i].se) - vals.begin() + 1;
	}
}

void SolvebyNoahzArk()
{
	cin >> n >> q;
	for (int i = 1; i <= n; ++i)
		cin >> r[i] >> h[i];
	for (int i = 1; i <= q; ++i)
		cin >> qr[i].fi >> qr[i].se;
	Initial();
	for (int i = 1; i <= n; ++i)
		grp[r[i]].pb(h[i]);
	for (int x = 1; x < maxn; ++x)
		sort(all(grp[x]));
	for (int i = 1; i <= q; ++i)
		question[qr[i].fi].pb(i);
	TFenwickTree ft;	
	ft.init(maxn);
	vector<int> res(q + 1);
	for (int i = maxn - 1; i >= 0; --i)
	{
		for (int x : grp[i])
			ft.update(x, ft.get(x) + 1);
		for (int x : question[i])
			res[x] = ft.get(qr[x].se);
	}
	for (int i = 1; i <= q; ++i)
		cout << res[i] << "\n";
}	

____vuviet__()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t-- > 0)
        SolvebyNoahzArk();
    return 0;
}

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