結果
問題 | No.728 ギブ and テイク |
ユーザー | hashiryo |
提出日時 | 2023-10-30 10:03:34 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 412 ms / 3,000 ms |
コード長 | 3,864 bytes |
コンパイル時間 | 2,217 ms |
コンパイル使用メモリ | 215,376 KB |
実行使用メモリ | 12,896 KB |
最終ジャッジ日時 | 2024-09-25 17:10:28 |
合計ジャッジ時間 | 6,588 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
// #define _GLIBCXX_DEBUG #include <bits/stdc++.h> // clang-format off std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;} std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;} std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;} std::ostream&operator<<(std::ostream&os,const __uint128_t &v){if(!v)os<<"0";__uint128_t tmp=v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;} #define checkpoint() (void(0)) #define debug(...) (void(0)) #define debugArray(x,n) (void(0)) #define debugMatrix(x,h,w) (void(0)) // clang-format on template <class T= long long> class WaveletMatrix { struct SuccinctIndexableDictionary { std::size_t len, blocks, zeros; std::vector<unsigned> bit, sum; SuccinctIndexableDictionary()= default; SuccinctIndexableDictionary(std::size_t len): len(len), blocks((len >> 5) + 1), bit(blocks, 0), sum(blocks, 0) {} void set(int k) { bit[k >> 5]|= 1U << (k & 31); } void build() { for (std::size_t i= 1; i < blocks; i++) sum[i]= sum[i - 1] + __builtin_popcount(bit[i - 1]); zeros= rank0(len); } bool operator[](int k) const { return (bit[k >> 5] >> (k & 31)) & 1; } std::size_t rank(std::size_t k) const { return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1))); } std::size_t rank0(std::size_t k) const { return k - rank(k); } }; std::size_t len, lg; std::vector<SuccinctIndexableDictionary> mat; std::vector<T> vec; public: WaveletMatrix()= default; WaveletMatrix(const std::vector<T> &v): len(v.size()), lg(32 - __builtin_clz(std::max<int>(len, 1))), mat(lg, len), vec(v) { std::sort(vec.begin(), vec.end()); vec.erase(std::unique(vec.begin(), vec.end()), vec.end()); std::vector<unsigned> cur(len), nex(len); for (int i= len; i--;) cur[i]= std::lower_bound(vec.begin(), vec.end(), v[i]) - vec.begin(); for (auto h= lg; h--; cur.swap(nex)) { for (std::size_t i= 0; i < len; i++) if ((cur[i] >> h) & 1) mat[h].set(i); mat[h].build(); std::array it{nex.begin(), nex.begin() + mat[h].zeros}; for (std::size_t i= 0; i < len; i++) *it[mat[h][i]]++= cur[i]; } } // k-th(0-indexed) smallest number in v[l,r) T kth_smallest(int l, int r, int k) const { assert(k < r - l); std::size_t ret= 0; for (auto h= lg; h--;) if (auto l0= mat[h].rank0(l), r0= mat[h].rank0(r); k >= r0 - l0) { k-= r0 - l0, ret|= 1 << h; l+= mat[h].zeros - l0, r+= mat[h].zeros - r0; } else l= l0, r= r0; return vec[ret]; } // k-th(0-indexed) largest number in v[l,r) T kth_largest(int l, int r, int k) const { return kth_smallest(l, r, r - l - k - 1); } // count i s.t. (l <= i < r) && (v[i] < ub) std::size_t count(int l, int r, T ub) const { std::size_t x= std::lower_bound(vec.begin(), vec.end(), ub) - vec.begin(); if (x >= 1u << lg) return r - l; if (x == 0) return 0; std::size_t ret= 0; for (auto h= lg; h--;) if (auto l0= mat[h].rank0(l), r0= mat[h].rank0(r); (x >> h) & 1) ret+= r0 - l0, l+= mat[h].zeros - l0, r+= mat[h].zeros - r0; else l= l0, r= r0; return ret; } // count i s.t. (l <= i < r) && (lb <= v[i] < ub) std::size_t count(int l, int r, T lb, T ub) const { return count(l, r, ub) - count(l, r, lb); } }; using namespace std; signed main() { cin.tie(0); ios::sync_with_stdio(0); int N; cin >> N; int A[N], L[N], R[N]; for (int i= 0; i < N; i++) cin >> A[i]; for (int i= 0; i < N; i++) cin >> L[i] >> R[i]; vector<int> r(N); for (int i= 0; i < N; i++) r[i]= A[i] + R[i]; WaveletMatrix wm(r); long long ans= 0; for (int i= 0; i < N; i++) { int left= lower_bound(A, A + N, A[i] - L[i]) - A; ans+= wm.count(left, i, A[i], 0x7fffffff); } cout << ans << "\n"; return 0; }