結果
問題 |
No.2710 How many more?
|
ユーザー |
![]() |
提出日時 | 2024-03-31 14:42:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 241 ms / 2,000 ms |
コード長 | 1,689 bytes |
コンパイル時間 | 1,700 ms |
コンパイル使用メモリ | 173,340 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-30 19:50:29 |
合計ジャッジ時間 | 5,030 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 17 |
ソースコード
#include "bits/stdc++.h" using namespace std; #define int long long #define rep(i, n) for (int i = 0; i < n; i++) // x以上の一番左側のイテレーターを返す // sortを忘れずに // x以上ものがなかったら1e9を返す int ijyou(const vector<int> &a, int x, int k, int k1) { int le = k; int ri = k1; if (a[k] >= x) return k; if (a[k1] < x) return 1e9; while (ri - le > 1) { int mid = (le + ri) / 2; if (x > a[mid]) { le = mid; } else { ri = mid; } } return ri; } // x以下の一番右側のイテレーターを返す // sortを忘れずに // x以下のものがなかったら1e9を返す int ika(const vector<int> &a, int x, int k, int k1) { if (a[k1] <= x) return k1; if (a[k] > x) return 1e9; int le = k; int ri = k1; while (ri - le > 1) { int mid = (le + ri) / 2; if (x >= a[mid]) le = mid; else ri = mid; } return ri - 1; } int yoriue(const vector<int> &a, int x, int k, int k1) { return ijyou(a, x + 1, k, k1); } int yorisita(const vector<int> &a, int x, int k, int k1) { return ika(a, x - 1, k, k1); } signed main() { int n, q; cin >> n >> q; vector<int> a(n); vector<int> b(n); rep(i, n) { cin >> a[i]; b[i] = a[i]; b[i] = 1e9 - a[i]; a[i] = 1e9 - a[i]; } sort(b.begin(), b.end()); rep(i, q) { int x, y; cin >> x >> y; x--; y--; int t = a[x]; int p = ika(b, t, 0, b.size() - 1); int t1 = a[y]; int p1 = ijyou(b, t1, 0, b.size() - 1); if (t == t1) { cout << 0 << endl; } else if (p > p1) { cout << 0 << endl; } else { cout << p1 - p - 1 << endl; } } }