Submission #1114221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114221		farica	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	1908 ms	70744 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 = lower_bound(V.begin(), V.end(), make_pair(a[i], i)) - V.begin();
    int j2 = lower_bound(V.begin(), V.end(), make_pair(a[i], -1)) - V.begin();
    upd(0, 0, V.size()-1, j, j, x*(i+1));
    upd(0, 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;
    V.clear();
    segm.assign(8*n, 0);
    lazy.assign(8*n, 0);
    a.assign(n, 0);
    for(int i=0; i<n; ++i) {
        a[i] = A[i];
        V.push_back({A[i], i});
    }
    for(int i=0; i<q; ++i) V.push_back({y[i], x[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;
}

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