結果
問題 | No.2422 regisys? |
ユーザー | ryota2357 |
提出日時 | 2023-07-19 12:07:51 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,651 bytes |
コンパイル時間 | 3,466 ms |
コンパイル使用メモリ | 135,528 KB |
実行使用メモリ | 10,696 KB |
最終ジャッジ日時 | 2023-10-19 14:36:21 |
合計ジャッジ時間 | 6,800 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 2 ms
4,348 KB |
testcase_04 | AC | 2 ms
4,348 KB |
testcase_05 | AC | 2 ms
4,348 KB |
testcase_06 | AC | 2 ms
4,348 KB |
testcase_07 | AC | 1 ms
4,348 KB |
testcase_08 | AC | 1 ms
4,348 KB |
testcase_09 | WA | - |
testcase_10 | AC | 2 ms
4,348 KB |
testcase_11 | WA | - |
testcase_12 | AC | 1 ms
4,348 KB |
testcase_13 | WA | - |
testcase_14 | AC | 2 ms
4,348 KB |
testcase_15 | WA | - |
testcase_16 | AC | 2 ms
4,348 KB |
testcase_17 | AC | 2 ms
4,348 KB |
testcase_18 | AC | 2 ms
4,348 KB |
testcase_19 | AC | 1 ms
4,348 KB |
testcase_20 | AC | 2 ms
4,348 KB |
testcase_21 | AC | 2 ms
4,348 KB |
testcase_22 | AC | 1 ms
4,348 KB |
testcase_23 | AC | 1 ms
4,348 KB |
testcase_24 | AC | 1 ms
4,348 KB |
testcase_25 | AC | 1 ms
4,348 KB |
testcase_26 | WA | - |
testcase_27 | AC | 2 ms
4,348 KB |
testcase_28 | AC | 1 ms
4,348 KB |
testcase_29 | AC | 1 ms
4,348 KB |
testcase_30 | AC | 2 ms
4,348 KB |
testcase_31 | AC | 32 ms
5,704 KB |
testcase_32 | AC | 41 ms
6,048 KB |
testcase_33 | AC | 31 ms
5,828 KB |
testcase_34 | AC | 17 ms
4,524 KB |
testcase_35 | AC | 39 ms
6,700 KB |
testcase_36 | AC | 30 ms
5,328 KB |
testcase_37 | AC | 43 ms
6,424 KB |
testcase_38 | AC | 31 ms
5,164 KB |
testcase_39 | AC | 21 ms
4,612 KB |
testcase_40 | WA | - |
testcase_41 | AC | 21 ms
4,668 KB |
testcase_42 | AC | 68 ms
9,240 KB |
testcase_43 | AC | 31 ms
5,520 KB |
testcase_44 | WA | - |
testcase_45 | AC | 60 ms
8,132 KB |
testcase_46 | WA | - |
testcase_47 | WA | - |
testcase_48 | AC | 76 ms
9,804 KB |
testcase_49 | WA | - |
testcase_50 | AC | 71 ms
9,764 KB |
testcase_51 | WA | - |
testcase_52 | AC | 31 ms
6,156 KB |
testcase_53 | WA | - |
testcase_54 | AC | 90 ms
10,696 KB |
testcase_55 | AC | 69 ms
9,688 KB |
testcase_56 | AC | 57 ms
7,640 KB |
testcase_57 | AC | 94 ms
10,424 KB |
testcase_58 | AC | 94 ms
10,432 KB |
testcase_59 | WA | - |
testcase_60 | AC | 95 ms
10,424 KB |
testcase_61 | AC | 2 ms
4,348 KB |
ソースコード
/*{{{ author: ryota2357 */ #include <algorithm> #include <cassert> #include <cmath> #include <cstdlib> #include <functional> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <tuple> #include <utility> #include <vector> namespace ryota2357 { template <class T1, class T2> inline std::istream& operator>>(std::istream& is, std::pair<T1, T2>& P) noexcept { return is >> P.first >> P.second; } template <class T> inline std::istream& operator>>(std::istream& is, std::vector<T>& V) noexcept { for (auto& v : V) is >> v; return is; } template <class T> inline std::ostream& operator<<(std::ostream& os, const std::vector<T>& V) noexcept { const auto n = V.size() - 1; for (int i = 0; i < n; ++i) os << V[i] << ' '; return os << V.back(); } inline void IN(void) noexcept { return; } template <class T, class... U> inline void IN(T& t, U&... u) noexcept { std::cin >> t; IN(u...); } template <class T> inline void OUT(const T& x) noexcept { std::cout << x << '\n'; } template <class T> inline bool chmax(T& a, const T& b) noexcept { return a < b ? a = b, true : false; } template <class T> inline bool chmin(T& a, const T& b) noexcept { return a > b ? a = b, true : false; } template <class T = int> inline T read(void) { T ret = 0; char c = getchar(); while ((c < '0' || '9' < c) && c != '-') c = getchar(); const bool f = (c == '-') && (c = getchar()); while ('0' <= c && c <= '9') { ret = 10 * ret + c - '0'; c = getchar(); } return f ? -ret : ret; } template <class T> inline T ceil_div(const T& a, const T& b) { assert(b != 0); return (a + (b - 1)) / b; } template <class T> inline T max(const std::vector<T>& v) { return *max_element(v.begin(), v.end()); } template <class T> inline T min(const std::vector<T>& v) { return *min_element(v.begin(), v.end()); } template <class F> inline constexpr decltype(auto) recursive(F&& f) { return [f = std::forward<F>(f)](auto&&... args) { return f(f, std::forward<decltype(args)>(args)...); }; } } // namespace ryota2357 using ll = long long; using pint = std::pair<int, int>; #define rep(i, a, b) for (ll i = (a); i < ll(b); ++i) #define repr(i, a, b) for (ll i = (a); i >= ll(b); --i) #define each(x, v) for (auto& x : v) #define All(x) (x).begin(), (x).end() #define AllR(x) (x).rbegin(), (x).rend() #define Sort(x) (sort((x).begin(), (x).end())) #define SortR(x) (sort((x).rbegin(), (x).rend())) #define Unique(x) (x.erase(unique((x).begin(), (x).end()), (x).end())) #define Fill(v, n) (fill((v), (v) + sizeof(v) / sizeof(*(v)), (v))) #define INF (1073741823) #define INFL (2305843009213693951ll) using namespace std; using namespace ryota2357; /*}}}*/ int solve(int n, int m, vector<pint> ab, vector<int> t0, vector<int> t1) { Sort(t0); Sort(t1); priority_queue<pint, vector<pint>, greater<>> small; priority_queue<int> large; rep(i, 0, n) { small.emplace(ab[i]); } each(x, t0) { while(small.size() && small.top().first <= x) { auto [a, b] = small.top(); small.pop(); large.emplace(min(a, b)); } if (large.empty()) { continue; } large.pop(); } vector<int> min_v; while (small.size()) { auto [a, b] = small.top(); small.pop(); min_v.push_back(min(a, b)); } while (large.size()) { min_v.push_back(large.top()); large.pop(); } SortR(min_v); each(x, t1) { if (min_v.empty()) { break; } if (min_v.back() <= x) { min_v.pop_back(); } } return min_v.size(); } // only n == m int expect(int n, int m, vector<pint> ab, vector<int> t0, vector<int> t1) { int ans = n; vector<int> idx(m); rep(i, 0, m) idx[i] = i; do { int cnt = 0; rep(i, 0, n) { auto [a, b] = ab[idx[i]]; if (i < t0.size()) { if (a <= t0[i]) { cnt += 1; } } else { if (min(a, b) <= t1[i - t0.size()]) { cnt += 1; } } } chmin(ans, n - cnt); } while(next_permutation(All(idx))); return ans; } int main() { int n, m; IN(n, m); vector<pint> ab(n); rep(i, 0, n) ab[i].first = read(); rep(i, 0, n) ab[i].second = read(); vector<int> t0, t1; rep(i, 0, m) { if (read() == 0) { t0.push_back(read()); } else { t1.push_back(read()); } } OUT(solve(n, m, ab, t0, t1)); // rep(_, 0, 100) { // int n = (rand() % 5) + 1, m = n; // vector<pint> ab(n); // vector<int> t0, t1; // rep(i, 0, n) { // ab[i] = {rand() % 100, rand() % 100}; // if (rand() % 2) { // t0.push_back(rand() % 100); // } else { // t1.push_back(rand() % 100); // } // } // int res = solve(n, m, ab, t0, t1); // int ans = expect(n, m, ab, t0, t1); // if (res != ans) { // cout << n << ' ' << m << endl; // rep(i, 0, n) cout << ab[i].first << " \n"[i == n-1]; // rep(i, 0, n) cout << ab[i].second << " \n"[i == n-1]; // rep(i, 0, t0.size()) cout << "0 " << t0[i] << endl; // rep(i, 0, t1.size()) cout << "1 " << t1[i] << endl; // // cout << endl; // cout << res << " / " << ans << endl; // break; // } // } return 0; }