Submission #102443

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

bubblesort2

#include <bits/stdc++.h>

using namespace std;

const int N = 500500;
const int MAGIC = 1616;

struct SegmentTree {
	vector<int> lz;
	vector<int> cnt;
	vector<int> val;
	void resize(int n) {
		lz.resize((n << 2) + 5);
		cnt.resize((n << 2) + 5);
		val.resize((n << 2) + 5);
	}
	void pull(int v) {
		cnt[v] = cnt[v << 1] + cnt[v << 1 | 1];
		val[v] = max(val[v << 1], val[v << 1 | 1]);
	}
	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 addVal(int v,int l,int r,int L,int R) {
		
	}
};

vector<int> countScans(vector<int> a,vector<int> x,vector<int> y) {
	// brute
	int n = a.size(), q = x.size();
	vector<int> f(n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < i; ++j) {
			f[i] += a[j] > a[i];
		} 
	}
	vector<int> ans;
	for (int i = 0; i < q; ++i) {
		// delval
		for (int j = x[i] + 1; j < n; ++j) {
			if (a[j] < a[x[i]]) {
				f[j]--;
			}
		}	
		a[x[i]] = y[i];
		for (int j = x[i] + 1; j < n; ++j) {
			if (a[j] < a[x[i]]) {
				f[j]++;
			}
		}
		f[x[i]] = 0;
		for (int j = 0; j < x[i]; ++j) {
			if (a[j] > a[x[i]]) {
				f[x[i]]++;
			}
		}
		ans.push_back(*max_element(f.begin(), f.end()));
	}
	return ans;
}

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