結果
問題 | No.1703 Much Matching |
ユーザー |
|
提出日時 | 2021-10-08 23:39:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 214 ms / 2,000 ms |
コード長 | 2,688 bytes |
コンパイル時間 | 946 ms |
コンパイル使用メモリ | 63,080 KB |
最終ジャッジ日時 | 2025-01-24 23:33:59 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
// https://atcoder.jp/contests/abc038/submissions/1165321#include <cstdio>#include <utility>#include <algorithm>#include <vector>#ifdef NO_UNLOCK_IO#define getchar_unlocked getchar#define putchar_unlocked putchar#endifstruct FastIO {static void scan(double &x) {scanf("%lf", &x);}template <class Integral>static void scan(Integral &x) {int k, m=0;x = 0;for (;;) {k = getchar_unlocked();if (k == '-') {m = 1;break;} else if ('0' <= k && k <= '9') {x = k-'0';break;}}for (;;) {k = getchar_unlocked();if (k < '0' || k > '9')break;x = x*10 + k-'0';}if (m)x = -x;}template <class Arithmetic, class... Rest>static void scan(Arithmetic &x, Rest&... y) {scan(x);scan(y...);}static void print(double x, char c) {printf("%.12f%c", x, c);}static void print(const char *x, char c) {printf("%s%c", x, c);}template <class Integral>static void print(Integral x, char c) {int s=0, m=0;char f[20];if (x < 0) {m = 1;x = -x;}while (x) {f[s++] = x%10;x /= 10;}if (!s)f[s++] = 0;if (m) putchar_unlocked('-');while (s--)putchar_unlocked(f[s]+'0');putchar_unlocked(c);}template <class Arithmetic>static void println(Arithmetic x) {print(x, '\n');}};template <class RandomIt>typename RandomIt::difference_type li_subseq(RandomIt first, RandomIt last, const typename RandomIt::value_type &inf) {std::vector<typename RandomIt::value_type> dp(last-first, inf);for (RandomIt i=first; i<last; ++i)*std::lower_bound(dp.begin(), dp.end(), *i) = *i;return std::lower_bound(dp.begin(), dp.end(), inf)-dp.begin();}struct {bool operator ()(const std::pair<int, int> &u, const std::pair<int, int> &v) {return u.first!=v.first? (u.first < v.first) : (u.second > v.second);}} comp;int main() {size_t xx, yy, N;FastIO::scan(xx, yy, N);std::vector<std::pair<int, int>> x(N);for (size_t i=0; i<N; ++i)FastIO::scan(x[i].first, x[i].second);std::sort(x.begin(), x.end(), comp);std::vector<int> a(N);for (size_t i=0; i<N; ++i)a[i] = x[i].second;FastIO::println(li_subseq(a.begin(), a.end(), 1<<29));return 0;}