Submission #979054

#	Time	Username	Problem	Language	Result	Execution time	Memory
979054		peterandvoi	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	1226 ms	60436 KiB

bubblesort2

#include <bits/stdc++.h>

#include "bubblesort2.h"

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

const int INF = int(1e8), N = int(1e6) + 5;

int n, m, q;
int s[4 * N], lz[4 * N];

void app(int id, int x) {
    s[id] += x;
    lz[id] += x;
}

void psh(int id) {
    app(id * 2, lz[id]);
    app(id * 2 + 1, lz[id]);
    lz[id] = 0;
}

void change(int i, int v, int x) {
    int id = 1, l = 1, r = m;
    while (l ^ r) {
        int md = (l + r) / 2;
        if (lz[id]) {
            psh(id);
        }
        id *= 2;
        if (i <= md) {
            app(id + 1, x);
            r = md;
        } else {
            l = md + 1;
            id += 1;
        }
    }
    s[id] += v;
    while (id > 1) {
        id /= 2;
        s[id] = max(s[id * 2], s[id * 2 + 1]);
    }
}

std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V){
	n = int(A.size());
    q = int(X.size());
    vector<int> res(q);
    vector<pair<int, int>> values;
    for (int i = 0; i < n; ++i) {
        values.emplace_back(A[i], i);
    }
    for (int i = 0; i < q; ++i) {
        values.emplace_back(V[i], X[i]);
    }
    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());
    auto upd = [&](int pos, int i, int x) {
        int v = pos;
        pos = lower_bound(values.begin(), values.end(), make_pair(pos, i)) - values.begin() + 1;
        change(pos, x * (i + INF), -x);
    };
    m = int(values.size());
    for (int i = 1; i < 4 * m; ++i) {
        s[i] = -INF;
    }
    for (int i = 0; i < n; ++i) {
        upd(A[i], i, 1);
    }
    for (int i = 0; i < q; ++i) {
        upd(A[X[i]], X[i], -1);
        upd(V[i], X[i], 1);
        res[i] = s[1];
        A[X[i]] = V[i];
    }
	return res;
}

Compilation message (stderr)

bubblesort2.cpp: In lambda function:
bubblesort2.cpp:66:13: warning: unused variable 'v' [-Wunused-variable]
   66 |         int v = pos;
      |             ^

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