結果
問題 | No.1703 Much Matching |
ユーザー | 箱星 |
提出日時 | 2021-10-08 23:39:35 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 202 ms / 2,000 ms |
コード長 | 2,688 bytes |
コンパイル時間 | 615 ms |
コンパイル使用メモリ | 61,312 KB |
実行使用メモリ | 18,304 KB |
最終ジャッジ日時 | 2024-07-23 07:59:27 |
合計ジャッジ時間 | 3,201 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 52 ms
6,784 KB |
testcase_07 | AC | 4 ms
5,376 KB |
testcase_08 | AC | 58 ms
7,040 KB |
testcase_09 | AC | 68 ms
7,680 KB |
testcase_10 | AC | 10 ms
5,376 KB |
testcase_11 | AC | 15 ms
5,376 KB |
testcase_12 | AC | 4 ms
5,376 KB |
testcase_13 | AC | 26 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 12 ms
5,376 KB |
testcase_16 | AC | 35 ms
5,504 KB |
testcase_17 | AC | 41 ms
5,888 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 88 ms
9,472 KB |
testcase_20 | AC | 11 ms
5,376 KB |
testcase_21 | AC | 105 ms
10,624 KB |
testcase_22 | AC | 40 ms
5,760 KB |
testcase_23 | AC | 31 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 5 ms
5,376 KB |
testcase_26 | AC | 20 ms
5,376 KB |
testcase_27 | AC | 46 ms
6,016 KB |
testcase_28 | AC | 85 ms
9,088 KB |
testcase_29 | AC | 16 ms
5,376 KB |
testcase_30 | AC | 23 ms
5,376 KB |
testcase_31 | AC | 3 ms
5,376 KB |
testcase_32 | AC | 44 ms
6,016 KB |
testcase_33 | AC | 30 ms
5,376 KB |
testcase_34 | AC | 4 ms
5,376 KB |
testcase_35 | AC | 9 ms
5,376 KB |
testcase_36 | AC | 202 ms
18,304 KB |
testcase_37 | AC | 2 ms
5,376 KB |
ソースコード
// 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 #endif struct 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; }