Submission #526612

#	Time	Username	Problem	Language	Result	Execution time	Memory
526612		Monarchuwu	Bubble Sort 2 (JOI18_bubblesort2)	C++17	60 / 100	9004 ms	8432 KiB

bubblesort2

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;

const int N = 5e5 + 5;
int n, q;
int a[N];

int b[N];
void update(int p, int old_val, int new_val) {
    b[p] = 0;
    for (int i = 0; i < p; ++i) b[p] += a[i] > new_val;
    for (int i = p + 1; i < n; ++i) {
        b[i] -= old_val > a[i];
        b[i] += new_val > a[i];
    }
}
int query() { return *max_element(b, b + n); }

vector<int> countScans(vector<int> A, vector<int> x, vector<int> v) {
    n = A.size(), q = x.size();
    for (int i = 0; i < n; ++i) update(i, 0, a[i] = A[i]);

    vector<int> ans;
    for (int i = 0; i < q; ++i) {
        update(x[i], a[x[i]], v[i]);
        a[x[i]] = v[i];
        ans.push_back(query());
    }
    return ans;
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

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