結果
問題 | No.2422 regisys? |
ユーザー |
![]() |
提出日時 | 2023-08-21 19:09:49 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 164 ms / 2,000 ms |
コード長 | 1,336 bytes |
コンパイル時間 | 888 ms |
コンパイル使用メモリ | 64,768 KB |
実行使用メモリ | 14,916 KB |
最終ジャッジ日時 | 2024-12-15 09:11:51 |
合計ジャッジ時間 | 8,496 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 61 |
ソースコード
/* -*- coding: utf-8 -*-** 2422.cc: No.2422 regisys? - yukicoder*/#include<cstdio>#include<vector>#include<set>#include<algorithm>#include<utility>using namespace std;/* constant */const int MAX_N = 200000;const int MAX_M = 200000;/* typedef */typedef vector<int> vi;typedef pair<int,int> pii;typedef multiset<int> msi;/* global variables */int as[MAX_N], bs[MAX_N];pii ps[MAX_N];vi tcs[2];/* subroutines *//* main */int main() {int n, m;scanf("%d%d", &n, &m);for (int i = 0; i < n; i++) scanf("%d", as + i);for (int i = 0; i < n; i++) scanf("%d", bs + i);for (int i = 0; i < n; i++) ps[i] = pii(as[i], bs[i]);sort(ps, ps + n);for (int i = 0; i < m; i++) {int ti, ci;scanf("%d%d", &ti, &ci);tcs[ti].push_back(ci);}vi &cs0 = tcs[0], &cs1 = tcs[1];sort(cs0.begin(), cs0.end());sort(cs1.begin(), cs1.end());msi bcs;int s = 0, k = 0;for (auto c0: cs0) {while (k < n && ps[k].first <= c0) bcs.insert(ps[k++].second);if (! bcs.empty()) {s++;auto sit = bcs.end();bcs.erase(--sit);}}while (k < n) bcs.insert(ps[k++].second);for (auto c1: cs1) {auto sit = bcs.upper_bound(c1);if (sit != bcs.begin()) {s++;bcs.erase(--sit);}}printf("%d\n", n - s);return 0;}