Submission #67538

#	Time	Username	Problem	Language	Result	Execution time	Memory
67538		imeimi2000	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	2773 ms	42908 KiB

bubblesort2

#include "bubblesort2.h"
#include <algorithm>

using namespace std;
typedef pair<int, int> pii;

int n, q, k;
pii comp[1000000];
const int inf = 1e8;
int seg[1 << 21];
int lay[1 << 21];
int fen[1000001];

void updatePoint(int i, int s, int e, int x, int v) {
    if (s == e) {
        seg[i] = v;
        lay[i] = 0;
        return;
    }
    
    seg[i << 1] += lay[i];
    seg[i << 1 | 1] += lay[i];
    lay[i << 1] += lay[i];
    lay[i << 1 | 1] += lay[i];
    lay[i] = 0;
    
    int m = (s + e) / 2;
    if (x <= m) updatePoint(i << 1, s, m, x, v);
    else updatePoint(i << 1 | 1, m + 1, e, x, v);
    seg[i] = max(seg[i << 1], seg[i << 1 | 1]) + lay[i];
}

void updateRange(int i, int s, int e, int x, int y, int v) {
    if (e < x || y < s) return;
    if (x <= s && e <= y) {
        seg[i] += v;
        lay[i] += v;
        return;
    }
    int m = (s + e) / 2;
    updateRange(i << 1, s, m, x, y, v);
    updateRange(i << 1 | 1, m + 1, e, x, y, v);
    seg[i] = max(seg[i << 1], seg[i << 1 | 1]) + lay[i];
}

void update(int i, int x) {
    while (i <= k) {
        fen[i] += x;
        i += i & -i;
    }
}

int query(int i) {
    int ret = 0;
    while (i) {
        ret += fen[i];
        i -= i & -i;
    }
    return ret;
}

int find(int i, int x) {
    return lower_bound(comp, comp + k, pii(x, i)) - comp + 1;
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
    for (int i = 0; i < (1 << 21); ++i) seg[i] = lay[i] = -inf;
	n = A.size();
	q = X.size();
	for (int i = 0; i < n; ++i) comp[k++] = pii(A[i], i);
	for (int i = 0; i < q; ++i) comp[k++] = pii(V[i], X[i]);
	sort(comp, comp + k);
	k = unique(comp, comp + k) - comp;
	for (int i = 0; i < n; ++i) {
        A[i] = find(i, A[i]);
        update(A[i], 1);
	}
	for (int i = 0; i < q; ++i) {
        V[i] = find(X[i], V[i]);
	}
	for (int i = 0; i < n; ++i) {
        updatePoint(1, 1, k, A[i], i - query(A[i] - 1));
	}
	vector<int> ret(q);
	for (int it = 0; it < q; ++it) {
        int i = X[it];
        int x = V[it];
        update(A[i], -1);
        updateRange(1, 1, k, A[i], k, 1);
        updatePoint(1, 1, k, A[i], -inf);
        
        A[i] = x;
        update(A[i], 1);
        updateRange(1, 1, k, A[i], k, -1);
        updatePoint(1, 1, k, A[i], i - query(A[i] - 1));
        ret[it] = seg[1];
	}
	return ret;
}

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