結果
問題 | No.2422 regisys? |
ユーザー |
![]() |
提出日時 | 2023-08-12 15:40:52 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 346 ms / 2,000 ms |
コード長 | 1,553 bytes |
コンパイル時間 | 916 ms |
コンパイル使用メモリ | 81,816 KB |
実行使用メモリ | 9,976 KB |
最終ジャッジ日時 | 2024-11-20 03:46:48 |
合計ジャッジ時間 | 9,087 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 61 |
ソースコード
//貧乏客から見ていく。一般人は買える商品の中でMMA部員にとって最も高価な商品を買う。逆も同様。プリキューで頑張る。#include <iostream>#include <vector>#include <queue>#include <algorithm>#define rep(i, n) for(i = 0; i < n; i++)using namespace std;typedef pair<int, int> P;int n, m;int prices[2][200000];vector<P> items[2]; //[0]: (a_i, 商品id), [1]: (b_i, 商品id)vector<P> pa; //(財布, 客タイプ)bool used[200000];priority_queue<P> que[2]; //[0]: (MMA部員にとっての価格, 商品id), [1]: (一般人にとっての価格, 商品id)int main() {int i;cin >> n >> m;items[0].resize(n); items[1].resize(n);pa.resize(m);rep(i, n) { cin >> prices[0][i]; items[0][i].first = prices[0][i]; items[0][i].second = i; }rep(i, n) { cin >> prices[1][i]; items[1][i].first = prices[1][i]; items[1][i].second = i; }rep(i, m) cin >> pa[i].second >> pa[i].first;sort(items[0].begin(), items[0].end());sort(items[1].begin(), items[1].end());sort(pa.begin(), pa.end());int cor[2] = {0};rep(i, m) {int t = pa[i].second;int wallet = pa[i].first;while (cor[t] < n && items[t][cor[t]].first <= wallet) {int item_id = items[t][cor[t]].second;que[t].push(P(prices[!t][item_id], item_id));cor[t]++;}while (!que[t].empty()) {P now = que[t].top(); que[t].pop();if (used[now.second] == false) {used[now.second] = true;break;}}}int ans = 0;rep(i, n) if (used[i]) ans++;cout << n - ans << endl;return 0;}