Submission #102503

#	Time	Username	Problem	Language	Result	Execution time	Memory
102503		IOrtroiii	Bubble Sort 2 (JOI18_bubblesort2)	C++14	0 / 100	38 ms	17908 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>

using namespace std;

using Arr = array<int, 3>;
const int N = 500500;
const int inf = 1e9;

int lz[N << 3];
int cnt[N << 3];
int val[N << 3];

void push(int v,int l,int r) {
	if (lz[v]) {
		val[v] += lz[v];
		if (l < r) {
			lz[v << 1] += lz[v];
			lz[v << 1 | 1] += lz[v];
		}
		lz[v] = 0;
	}
}

void upd(int v,int l,int r,int p,int x,int y) {
	push(v, l, r);
	if (p > r || p < l) return;
	if (l == r) {
		val[v] = x;
		cnt[v] = y;
		return;
	}
	int md = (l + r) >> 1;
	upd(v << 1, l, md, p, x, y);
	upd(v << 1 | 1, md + 1, r, p, x, y);
	val[v] = max(val[v << 1], val[v << 1 | 1]);
	cnt[v] = cnt[v << 1] + cnt[v << 1 | 1];
}

void add(int v,int l,int r,int L,int R,int x) {
	push(v, l, r);
	if (L > r || R < l) return;
	if (L <= l && r <= R) {
		lz[v] = x;
		push(v, l, r);
		return;
	}
	int md = (l + r) >> 1;
	add(v << 1, l, md, L, R, x);
	add(v << 1 | 1, md + 1, r, L, R, x);
	val[v] = max(val[v << 1], val[v << 1 | 1]);
}

int get(int v,int l,int r,int L,int R) {
	push(v, l, r);
	if (L > r || R < l) return 0;
	if (L <= l && r <= R) return cnt[v];
	int md = (l + r) >> 1;
	return get(v << 1, l, md, L, R) + get(v << 1 | 1, md + 1, r, L, R); 
}

int now[N], pos[N];

vector<int> countScans(vector<int> a, vector<int> x, vector<int> y) {
	int n = a.size(), q = x.size();
	vector<Arr> vals;
	for (int i = 0; i < n; ++i) {
		vals.push_back({a[i], i, i});
	}
	for (int i = 0; i < q; ++i) {
		vals.push_back({y[i], x[i], i + n});
	}
	sort(vals.begin(), vals.end());
	int sz = n + q;
	memset(val, -69, sizeof val);
	for (int i = 0; i < sz; ++i) {
		printf("%d %d %d\n", vals[i][0], vals[i][1], vals[i][2]);
		int p = vals[i][1], id = vals[i][2];
		if (id >= n) {
			pos[id - n] = i;
		} else {
			int nw = p - get(1, 0, sz - 1, 0, i);
			now[p] = i;
			upd(1, 0, sz - 1, p, nw, 1);
		}
	} 
	vector<int> ans(q);
	for (int i = 0; i < q; ++i) {
		add(1, 0, sz - 1, now[x[i]], sz - 1, 1);
		upd(1, 0, sz - 1, now[x[i]], -inf, 0);
		now[x[i]] = pos[i];
		int nw = x[i] - get(1, 0, sz - 1, 0, now[x[i]]);
		add(1, 0, sz - 1, now[x[i]], sz - 1, -1);
		upd(1, 0, sz - 1, now[x[i]], nw, 1);
		ans[i] = val[1];
	}
	return ans;
}

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