結果

問題 No.1703 Much Matching
ユーザー kiyoshi0205kiyoshi0205
提出日時 2021-10-08 22:17:46
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 1,955 bytes
コンパイル時間 475 ms
コンパイル使用メモリ 45,276 KB
実行使用メモリ 4,580 KB
最終ジャッジ日時 2023-09-30 10:40:12
合計ジャッジ時間 4,669 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 RE -
testcase_07 AC 3 ms
4,376 KB
testcase_08 RE -
testcase_09 RE -
testcase_10 AC 4 ms
4,380 KB
testcase_11 AC 8 ms
4,376 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 RE -
testcase_14 AC 1 ms
4,376 KB
testcase_15 AC 7 ms
4,376 KB
testcase_16 RE -
testcase_17 RE -
testcase_18 AC 2 ms
4,376 KB
testcase_19 RE -
testcase_20 AC 4 ms
4,380 KB
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 AC 2 ms
4,380 KB
testcase_25 AC 3 ms
4,376 KB
testcase_26 AC 11 ms
4,580 KB
testcase_27 RE -
testcase_28 RE -
testcase_29 AC 8 ms
4,380 KB
testcase_30 RE -
testcase_31 AC 2 ms
4,380 KB
testcase_32 RE -
testcase_33 RE -
testcase_34 AC 2 ms
4,376 KB
testcase_35 AC 5 ms
4,380 KB
testcase_36 RE -
testcase_37 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

void pakuri_sort(int N, ll A[]) {
	const int b = 9;
	ll tmp[100001];
	rep(k, 4) {
		int kazu[1 << b] = {}, kazu2[1 << b] = {};
		rep(i, N) kazu[A[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];
		for (int i = N - 1; i >= 0; i--) tmp[--kazu[A[i] >> k * b & ((1 << b) - 1)]] = A[i];
		k++;
		rep(i, N) kazu2[tmp[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];
		for (int i = N - 1; i >= 0; i--) A[--kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp[i];
	}
}

int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);

  getint();getint();
	int N = getint();
	ll HW[100000];
	rep(i, N) {
		HW[i] = ((ll)getint() << 18) + 100000 - getint();
	}
	pakuri_sort(N, HW);

	int dp[100000];
	int k = 0;
	int saidai = 0;
	const int m = (1 << 18) - 1;
	rep(i, N) {
		int h = 100000 - (HW[i] & m);
		if (saidai < h) {
			dp[k++] = h;
			saidai = h;
		}
		else {
			auto itr = lower_bound(dp, dp + k, h);
			if (itr == dp + k - 1) saidai = h;
			*itr = h;
		}
	}

	printf("%d", k);

	Would you please return 0;
}
0