Submission #1114213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114213		farica	Bubble Sort 2 (JOI18_bubblesort2)	C++17	Compilation error	0 ms	0 KiB

bubblesort2

#include <bits/stdc++.h>

using namespace std;
using vi = vector<int>;

vi a, segm, lazy;
vector<pair<int,int>>V;

void propagate(int pos, int l, int r) {
    if(l==r) return;
    int m = (l+r)/2, right = pos + 2 * (m-l+1);
    lazy[pos+1] += lazy[pos];
    lazy[right] += lazy[pos];
    segm[pos+1] += lazy[pos];
    segm[right] += lazy[pos];
    lazy[pos] = 0;
}

void upd(int pos, int l, int r, int L, int R, int val) {
    if(l > R or r < L) return;
    propagate(pos, l, r);
    if(l >= L && r <= R) {
        segm[pos] += val;
        lazy[pos] += val;
        return;
    }
    int m = (l+r)/2, right = pos + 2 * (m-l+1);
    if(L <= m) upd(pos+1, l, m, L, R, val);
    if(R >= m+1) upd(right, m+1, r, L, R, val);
    segm[pos] = max(segm[pos+1], segm[right]);
}

void add(int i, int x) {
    int j = V.lower_bound(V.begin(), V.end(), make_pair(a[i], i)) - V.begin(), j2 = V.lower_bound(V.begin(), V.end(), make_pair(a[i], -1));
    upd(1, 0, V.size()-1, j, j, x*(i+1));
    upd(1, 0, V.size()-1, j2, V.size()-1, -x);
}

vi countScans(vi A, vi x, vi y) {
    int n = A.size(), q = x.size();
    vi ans;
    segm.assign(4*n, 0);
    lazy.assign(4*n, 0);
    a.assign(n, 0);
    for(int i=0; i<n; ++i) {
        a[i] = A[i];
        V.push_back({A[i], i});
    }
    sort(V.begin(), V.end());
    V.erase(unique(V.begin(), V.end()), V.end());
    for(int i=0; i<n; ++i) add(i, 1);
    for(int i=0; i<q; ++i) {
        add(x[i], -1);
        a[x[i]] = y[i];
        add(x[i], 1);
        ans.push_back(segm[0]);
    }
    return ans;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'void add(int, int)':
bubblesort2.cpp:34:15: error: 'class std::vector<std::pair<int, int> >' has no member named 'lower_bound'
   34 |     int j = V.lower_bound(V.begin(), V.end(), make_pair(a[i], i)) - V.begin(), j2 = V.lower_bound(V.begin(), V.end(), make_pair(a[i], -1));
      |               ^~~~~~~~~~~
bubblesort2.cpp:36:27: error: 'j2' was not declared in this scope; did you mean 'j'?
   36 |     upd(1, 0, V.size()-1, j2, V.size()-1, -x);
      |                           ^~
      |                           j