結果
問題 | No.2667 Constrained Permutation |
ユーザー | みここ |
提出日時 | 2024-03-08 22:03:43 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 474 ms / 2,000 ms |
コード長 | 1,064 bytes |
コンパイル時間 | 894 ms |
コンパイル使用メモリ | 85,260 KB |
実行使用メモリ | 8,424 KB |
最終ジャッジ日時 | 2024-09-29 19:39:34 |
合計ジャッジ時間 | 9,384 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 46 |
ソースコード
#include <algorithm>#include <iostream>#include <queue>using namespace std;typedef long long ll;typedef pair<int, int> P;int main(){int n;cin >> n;P p[200005];for (int i = 0; i < n; i++){cin >> p[i].first >> p[i].second;}int l = 0;sort(p, p + n);for (int i = 0; i < n; i++){l = max(l, p[i].first - (i + 1));}ll ok = l - 1, ng = 2000000000;while (abs(ok - ng) > 1){ll k = (ok + ng) / 2;int j = 0;priority_queue<ll, vector<ll>, greater<ll>> que;bool f = true;for (int i = 1; i <= n; i++){while (j < n && p[j].first <= i + k){que.push(p[j++].second);}if (!que.size() || que.top() < i + k){f = false;break;}que.pop();}if (f){ok = k;}else{ng = k;}}cout << ok - l + 1 << endl;}