Submission #164082

#	Time	Username	Problem	Language	Result	Execution time	Memory
164082		dolphingarlic	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2857 ms	47572 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

const int INF = INT_MAX / 2;

int N, S;
int segtree[4000000], lazy[4000000];

void push_lazy(int node, int l, int r) {
	segtree[node] += lazy[node];
	if (l != r) {
		lazy[node * 2] += lazy[node];
		lazy[node * 2 + 1] += lazy[node];
	}
	lazy[node] = 0;
}

int query(int node) {
	return segtree[node] + lazy[node];
}
void update(int a, int b, int val, int node = 1, int l = 0, int r = S) {
	if (a == b || a >= r || b <= l) return;
	if (a <= l && b >= r) {
		lazy[node] += val;
		return;
	}
	push_lazy(node, l, r);

	int mid = (l + r) / 2;
	update(a, b, val, node * 2, l, mid);
	update(a, b, val, node * 2 + 1, mid, r);
	segtree[node] = max(query(node * 2), query(node * 2 + 1));
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
    int Q = X.size();
	N = A.size();
    vector<int> answer(Q);

	vector<pair<int, int>> compressed;
	FOR(i, 0, N) compressed.push_back({A[i], i});
	FOR(i, 0, Q) compressed.push_back({V[i], X[i]});
	sort(compressed.begin(), compressed.end());
	compressed.erase(unique(compressed.begin(), compressed.end()), compressed.end());

	const auto insert = [&](int a, int b) {
		int pos = lower_bound(compressed.begin(), compressed.end(), make_pair(a, b)) - compressed.begin();
		update(pos, pos + 1, INF + b);
		update(pos + 1, S, -1);
	};
	const auto erase = [&](int a, int b) {
		int pos = lower_bound(compressed.begin(), compressed.end(), make_pair(a, b)) - compressed.begin();
		update(pos, pos + 1, -(INF + b));
		update(pos + 1, S, 1);
	};

	S = compressed.size();
	update(0, S, -INF);
	FOR(i, 0, N) insert(A[i], i);

    FOR(i, 0, Q) {
		erase(A[X[i]], X[i]);
		insert(V[i], X[i]);
		A[X[i]] = V[i];
		
		answer[i] = query(1);
    }

    return answer;
}

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