fork download

copy

 
struct fenwik {
    vector<int> t;
    int allsum;
 
    fenwik() {}
    fenwik(int n) {
        t = vector<int>(n, 0);
        allsum = 0;
    }
    int as() {
        return allsum;
    }
    int get(int r) {
        r++;
        int ans = 0;
        while (r > 0) {
            ans += t[r - 1];
            r -= r & -r;
        }
        return ans;
    }
    void add(int pos) {
        allsum++;
        pos++;
        while (pos <= t.size()) {
            t[pos - 1]++;
            pos += pos & -pos;
        }
    }
};
 
vector<int> tree[4 * maxn];
fenwik bit[4 * maxn];
 
int pos[maxn], a[maxn];
 
void build(int v, int tl, int tr) {
    bit[v] = fenwik(tr - tl + 1);
    if (tl == tr) {
        tree[v].pb(pos[tl]);
        return;
    }
    int tm = (tl + tr) >> 1;
    build(v<<1, tl, tm);
    build(v<<1|1, tm + 1, tr);
    merge(all(tree[v<<1]), all(tree[v<<1|1]), back_inserter(tree[v]));
}
 
void upd(int v, int tl, int tr, int pos) {
    int cur_it = lower_bound(all(tree[v]), ::pos[pos]) - tree[v].begin();
    bit[v].add(cur_it);
 
    if (tl == tr)
        return;
    int tm = (tl + tr) >> 1;
    if (pos <= tm)
        upd(v<<1, tl, tm, pos);
    else
        upd(v<<1|1, tm + 1, tr, pos);
}
 
int get(int v, int tl, int tr, int l, int r, int x) {
    if (l > r)
        return 0;
    if (tl == l && tr == r) {
        int cur_it = upper_bound(all(tree[v]), x) - tree[v].begin() - 1;
        return bit[v].as() - bit[v].get(cur_it);
    }
    int tm = (tl + tr) >> 1;
    return get(v<<1  , tl, tm, l, min(r, tm), x) + 
           get(v<<1|1, tm + 1, tr, max(l, tm + 1), r, x);
}
 
int main() {
    files;
    // freopen("input.txt", "r", stdin);
    int n, k;
    read(n, k);
 
    for (int i = 0; i < n; i++) {
        read(a[i]);
        a[i]--;
    }
    for (int i = 0; i < n; i++) {
        int x;
        read(x);
        x--;
 
        pos[x] = i;
    }
    build(1, 0, n - 1);
 
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        int x = a[i];
        int res = 0;
 
        int r = x - k - 1;
        res += get(1, 0, n - 1, 0, r, pos[x]);
 
        int l = x + k + 1;
        res += get(1, 0, n - 1, l, n - 1, pos[x]);
 
        ans += res;
        upd(1, 0, n - 1, x);
    }
    cout << ans;
    return 0;
}

prog.cpp:3:5: error: ‘vector’ does not name a type
     vector<int> t;
     ^~~~~~
prog.cpp: In constructor ‘fenwik::fenwik(int)’:
prog.cpp:8:9: error: ‘t’ was not declared in this scope
         t = vector<int>(n, 0);
         ^
prog.cpp:8:13: error: ‘vector’ was not declared in this scope
         t = vector<int>(n, 0);
             ^~~~~~
prog.cpp:8:20: error: expected primary-expression before ‘int’
         t = vector<int>(n, 0);
                    ^~~
prog.cpp: In member function ‘int fenwik::get(int)’:
prog.cpp:18:20: error: ‘t’ was not declared in this scope
             ans += t[r - 1];
                    ^
prog.cpp: In member function ‘void fenwik::add(int)’:
prog.cpp:26:23: error: ‘t’ was not declared in this scope
         while (pos <= t.size()) {
                       ^
prog.cpp: At global scope:
prog.cpp:33:1: error: ‘vector’ does not name a type
 vector<int> tree[4 * maxn];
 ^~~~~~
prog.cpp:34:16: error: ‘maxn’ was not declared in this scope
 fenwik bit[4 * maxn];
                ^~~~
prog.cpp:36:9: error: ‘maxn’ was not declared in this scope
 int pos[maxn], a[maxn];
         ^~~~
prog.cpp:36:18: error: ‘maxn’ was not declared in this scope
 int pos[maxn], a[maxn];
                  ^~~~
prog.cpp: In function ‘void build(int, int, int)’:
prog.cpp:39:5: error: ‘bit’ was not declared in this scope
     bit[v] = fenwik(tr - tl + 1);
     ^~~
prog.cpp:41:9: error: ‘tree’ was not declared in this scope
         tree[v].pb(pos[tl]);
         ^~~~
prog.cpp:41:20: error: ‘pos’ was not declared in this scope
         tree[v].pb(pos[tl]);
                    ^~~
prog.cpp:47:15: error: ‘tree’ was not declared in this scope
     merge(all(tree[v<<1]), all(tree[v<<1|1]), back_inserter(tree[v]));
               ^~~~
prog.cpp:47:25: error: ‘all’ was not declared in this scope
     merge(all(tree[v<<1]), all(tree[v<<1|1]), back_inserter(tree[v]));
                         ^
prog.cpp:47:68: error: ‘back_inserter’ was not declared in this scope
     merge(all(tree[v<<1]), all(tree[v<<1|1]), back_inserter(tree[v]));
                                                                    ^
prog.cpp:47:69: error: ‘merge’ was not declared in this scope
     merge(all(tree[v<<1]), all(tree[v<<1|1]), back_inserter(tree[v]));
                                                                     ^
prog.cpp: In function ‘void upd(int, int, int, int)’:
prog.cpp:51:34: error: ‘tree’ was not declared in this scope
     int cur_it = lower_bound(all(tree[v]), ::pos[pos]) - tree[v].begin();
                                  ^~~~
prog.cpp:51:41: error: ‘all’ was not declared in this scope
     int cur_it = lower_bound(all(tree[v]), ::pos[pos]) - tree[v].begin();
                                         ^
prog.cpp:51:44: error: ‘::pos’ has not been declared
     int cur_it = lower_bound(all(tree[v]), ::pos[pos]) - tree[v].begin();
                                            ^~
prog.cpp:51:54: error: ‘lower_bound’ was not declared in this scope
     int cur_it = lower_bound(all(tree[v]), ::pos[pos]) - tree[v].begin();
                                                      ^
prog.cpp:52:5: error: ‘bit’ was not declared in this scope
     bit[v].add(cur_it);
     ^~~
prog.cpp: In function ‘int get(int, int, int, int, int, int)’:
prog.cpp:67:38: error: ‘tree’ was not declared in this scope
         int cur_it = upper_bound(all(tree[v]), x) - tree[v].begin() - 1;
                                      ^~~~
prog.cpp:67:45: error: ‘all’ was not declared in this scope
         int cur_it = upper_bound(all(tree[v]), x) - tree[v].begin() - 1;
                                             ^
prog.cpp:67:49: error: ‘upper_bound’ was not declared in this scope
         int cur_it = upper_bound(all(tree[v]), x) - tree[v].begin() - 1;
                                                 ^
prog.cpp:68:16: error: ‘bit’ was not declared in this scope
         return bit[v].as() - bit[v].get(cur_it);
                ^~~
prog.cpp:71:44: error: ‘min’ was not declared in this scope
     return get(v<<1  , tl, tm, l, min(r, tm), x) +
                                            ^
prog.cpp:72:49: error: ‘max’ was not declared in this scope
            get(v<<1|1, tm + 1, tr, max(l, tm + 1), r, x);
                                                 ^
prog.cpp: In function ‘int main()’:
prog.cpp:76:5: error: ‘files’ was not declared in this scope
     files;
     ^~~~~
prog.cpp:79:14: error: ‘read’ was not declared in this scope
     read(n, k);
              ^
prog.cpp:82:14: error: ‘a’ was not declared in this scope
         read(a[i]);
              ^
prog.cpp:90:9: error: ‘pos’ was not declared in this scope
         pos[x] = i;
         ^~~
prog.cpp:94:5: error: ‘ll’ was not declared in this scope
     ll ans = 0;
     ^~
prog.cpp:96:17: error: ‘a’ was not declared in this scope
         int x = a[i];
                 ^
prog.cpp:100:39: error: ‘pos’ was not declared in this scope
         res += get(1, 0, n - 1, 0, r, pos[x]);
                                       ^~~
prog.cpp:105:9: error: ‘ans’ was not declared in this scope
         ans += res;
         ^~~
prog.cpp:108:5: error: ‘cout’ was not declared in this scope
     cout << ans;
     ^~~~
prog.cpp:108:13: error: ‘ans’ was not declared in this scope
     cout << ans;
             ^~~

Standard output is empty