verify/waveletmatrix_rangefreq.test.cpp

View this file on GitHub
Last update: 2020-04-15 15:25:38+09:00
Problem: https://yukicoder.me/problems/1937

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/1937"
#include "bits/stdc++.h"

using namespace std;

using i64 = long long;


#include "../lib/classes/bitvector.cpp"
#include "../lib/classes/waveletmatrix.cpp"


signed main(){

    int n;
    cin >> n;
    vector<i64> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        a[i] += 2000000000;
    }
    vector<i64> l(n), r(n);
    for(int i = 0; i < n; ++i){
        cin >> l[i] >> r[i];
        l[i] = a[i] - l[i];
        r[i] = a[i] + r[i];
    }

    WaveletMatrix<i64, 35> l_wm(l);
    WaveletMatrix<i64, 35> r_wm(r);

    i64 ans = 0;
    for(int i = 0; i < n; ++i){
        int l_idx = distance(a.begin(), lower_bound(a.begin(), a.end(), l[i]));
        int r_idx = distance(a.begin(), upper_bound(a.begin(), a.end(), r[i])) - 1;
        ans += r_wm.count_range(l_idx, i, a[i], (1LL << 34));
        ans += l_wm.count_range(i + 1, r_idx + 1, 0, a[i] + 1);
    }
    cout << (ans >> 1) << endl;

}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.9.0/x64/lib/python3.9/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/opt/hostedtoolcache/Python/3.9.0/x64/lib/python3.9/site-packages/onlinejudge_verify/languages/cplusplus.py", line 193, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.9.0/x64/lib/python3.9/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 399, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/opt/hostedtoolcache/Python/3.9.0/x64/lib/python3.9/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 258, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: bits/stdc++.h: line -1: no such header