Submission #133873

#	Time	Username	Problem	Language	Result	Execution time	Memory
133873		osaaateiasavtnl	Bubble Sort 2 (JOI18_bubblesort2)	C++14	0 / 100	41 ms	32632 KiB

bubblesort2

#include<bits/stdc++.h>
using namespace std;
#define app push_back
#define ii pair <int, int>
#define mp make_pair
const int N = 1e6 + 7;
int mx[N << 2], add[N << 2];
void push(int v) {
    if (add[v]) {
        for (int i = v * 2 + 1; i <= v * 2 + 2; ++i) {
            mx[i] += add[v]; add[i] += add[v];
        }   
        add[v] = 0;
    }
}   
void relax(int v) {
    mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
}   
void upd(int v, int tl, int tr, int p, int x) {
    if (tl == tr) {
        mx[v] = x;
        return;
    }   
    int tm = (tl + tr) >> 1;
    push(v);
    if (p <= tm) upd(v * 2 + 1, tl, tm, p, x);
    else upd(v * 2 + 2, tm + 1, tr, p, x);
    relax(v);
}
void add_(int v, int tl, int tr, int l, int r, int x) {
    if (tr < l || r < tl) return;
    if (l <= tl && tr <= r) {
        mx[v] += x; add[v] += x;
        return;
    }   
    int tm = (tl + tr) >> 1;
    push(v);
    add_(v * 2 + 1, tl, tm, l, r, x); add_(v * 2 + 2, tm + 1, tr, l, r, x);
    relax(v);
}  

int f[N];
void addf(int i, int x) {
    for (; i < N; i |= i + 1) f[i] += x;
}   
int get(int i) {
    int ans = 0;
    for (; i >= 0; i &= i + 1, --i) ans += f[i];
    return ans;
}   

vector <int> countScans(vector <int> a, vector <int> p, vector <int> x) {
    int n = a.size(), q = p.size();
    vector <ii> v;
    for (int i = 0; i < n; ++i) {
        v.app({a[i], i});
    }   
    for (int i = 0; i < q; ++i) {
        v.app({x[i], p[i]});
    }   
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    for (int i = 0; i < n; ++i) {
        a[i] = lower_bound(v.begin(), v.end(), mp(a[i], i)) - v.begin();
    }   
    for (int i = 0; i < q; ++i) {
        x[i] = lower_bound(v.begin(), v.end(), mp(x[i], p[i])) - v.begin();
    }   
    for (int i = 0; i < (N << 2); ++i) mx[i] = -N;
    vector <int> t;
    for (int i = 0; i < n; ++i) {
        t.app(a[i]);
    }
    sort(t.begin(), t.end()); t.resize(unique(t.begin(), t.end()) - t.begin());
    for (int i = 0; i < n; ++i) {
        int p = lower_bound(t.begin(), t.end(), a[i]) - t.begin();
        upd(0, 0, N, a[i], i - p);
    }   
    vector <int> ans;
    for (int i = 0; i < q; ++i) {
        if (a[i] < x[i]) {
            add_(0, 0, N, min(a[i], x[i]) + 1, max(a[i], x[i]) - 1, -1);
        }
        else {
            add_(0, 0, N, min(a[i], x[i]) + 1, max(a[i], x[i]) - 1, 1);
        }
           
        upd(0, 0, N, a[i], -N);
        addf(a[i], -1);
        int pp = get(x[i]);
        upd(0, 0, N, pp, p[i] - pp);
        addf(x[i], 1);

        a[i] = x[i];
        ans.app(mx[0]);
    }   
    return ans;
}   
#ifdef HOME
signed main() {
    freopen("input.txt", "r", stdin);



}   
#endif  

• Subtask 1: 0 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40