結果
問題 | No.728 ギブ and テイク |
ユーザー | xuzijian629 |
提出日時 | 2018-09-06 16:20:07 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 793 ms / 3,000 ms |
コード長 | 2,769 bytes |
コンパイル時間 | 2,186 ms |
コンパイル使用メモリ | 141,392 KB |
実行使用メモリ | 95,744 KB |
最終ジャッジ日時 | 2024-05-01 23:00:04 |
合計ジャッジ時間 | 11,015 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 11 ms
27,776 KB |
testcase_01 | AC | 11 ms
27,904 KB |
testcase_02 | AC | 10 ms
27,776 KB |
testcase_03 | AC | 11 ms
28,004 KB |
testcase_04 | AC | 10 ms
27,904 KB |
testcase_05 | AC | 11 ms
27,776 KB |
testcase_06 | AC | 11 ms
27,904 KB |
testcase_07 | AC | 11 ms
27,976 KB |
testcase_08 | AC | 11 ms
27,776 KB |
testcase_09 | AC | 11 ms
27,904 KB |
testcase_10 | AC | 11 ms
27,904 KB |
testcase_11 | AC | 11 ms
27,972 KB |
testcase_12 | AC | 11 ms
27,904 KB |
testcase_13 | AC | 43 ms
31,232 KB |
testcase_14 | AC | 66 ms
33,736 KB |
testcase_15 | AC | 34 ms
30,336 KB |
testcase_16 | AC | 62 ms
33,128 KB |
testcase_17 | AC | 54 ms
32,668 KB |
testcase_18 | AC | 556 ms
75,344 KB |
testcase_19 | AC | 604 ms
78,412 KB |
testcase_20 | AC | 688 ms
87,524 KB |
testcase_21 | AC | 615 ms
81,452 KB |
testcase_22 | AC | 235 ms
48,056 KB |
testcase_23 | AC | 148 ms
40,820 KB |
testcase_24 | AC | 465 ms
67,372 KB |
testcase_25 | AC | 479 ms
67,128 KB |
testcase_26 | AC | 227 ms
47,140 KB |
testcase_27 | AC | 793 ms
95,744 KB |
testcase_28 | AC | 568 ms
95,620 KB |
testcase_29 | AC | 11 ms
27,776 KB |
testcase_30 | AC | 10 ms
27,904 KB |
testcase_31 | AC | 11 ms
27,796 KB |
testcase_32 | AC | 11 ms
27,904 KB |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <stack> #include <queue> #include <map> #include <chrono> #include <random> #include <unordered_map> #include <cassert> #pragma GCC optimize("O3") #pragma comment(linker, "STACK:36777216") using namespace std; using i64 = int64_t; constexpr i64 MOD = 1e9 + 7; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); using vi = vector<i64>; using vvi = vector<vi>; using vvvi = vector<vvi>; using ii = pair<i64, i64>; class RangeCount { const int ST_SIZE = (1 << 20) - 1; int n; vi data; vvi segtree; void init(int k, int l, int r) { if (r - l == 1) { segtree[k].push_back(data[l]); } else { int lch = k * 2 + 1; int rch = k * 2 + 2; init(lch, l, (l + r) / 2); init(rch, (l + r) / 2, r); segtree[k].resize(r - l); merge(segtree[lch].begin(), segtree[lch].end(), segtree[rch].begin(), segtree[rch].end(), segtree[k].begin()); } } // number of x in [i, j) int query(int i, int j, i64 x, int k, int l, int r) { if (j <= l || r <= i) { return 0; } if (i <= l && r <= j) { return int(upper_bound(segtree[k].begin(), segtree[k].end(), x) - segtree[k].begin()); } int lc = query(i, j, x, k * 2 + 1, l, (l + r) / 2); int rc = query(i, j, x, k * 2 + 2, (l + r) / 2, r); return lc + rc; } public: RangeCount(vi v) { n = int(v.size()); data = vi(v); segtree = vvi(ST_SIZE); init(0, 0, n); } int exact(int i, int j, i64 x) { return query(i, j, x, 0, 0, n) - query(i, j, x - 1, 0, 0, n); } int le(int i, int j, i64 x) { return query(i, j, x, 0, 0, n); } int lt(int i, int j, i64 x) { return query(i, j, x - 1, 0, 0, n); } int ge(int i, int j, i64 x) { return query(i, j, 1e18, 0, 0, n) - query(i, j, x - 1, 0, 0, n); } int gt(int i, int j, i64 x) { return query(i, j, 1e18, 0, 0, n) - query(i, j, x, 0, 0, n); } }; int main() { int n; cin >> n; vi as, rs, ds; for (int i = 0; i < n; i++) { i64 a; cin >> a; as.push_back(a); } for (int i = 0; i < n; i++) { i64 l, r; cin >> l >> r; rs.push_back(r); ds.push_back(as[i] - l); } i64 ans = 0; RangeCount cnt(ds); for (int i = 0; i < n; i++) { i64 lim = as[i] + rs[i]; int j = lower_bound(as.begin(), as.end(), lim + 1) - as.begin(); ans += cnt.le(i + 1, j, as[i]); } cout << ans << endl; }