Submission #65237

#	Time	Username	Problem	Language	Result	Execution time	Memory
65237		shoemakerjo	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	7098 ms	447220 KiB

bubblesort2

#include "bubblesort2.h"

#include <bits/stdc++.h>
using namespace std;
#define dec nice_macro

#define maxn 1000010
int N, Q;

int seg[maxn*4];
int delt[maxn*4];
multiset<int> leaves[maxn]; //(think we want this stuff)
map<int, int> dec;
int ovals[maxn]; //number less than or equal to each value in initial sequence
int cvals[maxn];


int query() {
	//just return the top of the segment tree plus the deltas
	return seg[0];
}

void av(int ai, int val, int ss, int se, int si) {
	if (ss == se) {
		leaves[ss].insert(val);
		seg[si] = delt[si] + *leaves[ss].rbegin();
		return;
	}
	int mid = (ss+se)/2;
	if (ai <= mid) {
		av(ai, val, ss, mid, si*2+1);
	}
	else av(ai, val, mid+1, se, si*2+2);

	seg[si] = delt[si] + max(seg[si*2+1], seg[si*2+2]); 
}

void addval(int ai, int val) {
	av(ai, val, 0, N+Q, 0);
}

void rv(int ai, int val ,int ss, int se, int si) {
	if (ss == se) {
		leaves[ss].erase(leaves[ss].find(val));
		if (leaves[ss].size() == 0) {
			seg[si] = -1234567890;
		}
		else {
			seg[si] = delt[si] + *leaves[ss].rbegin();
		}
		return;
	}
	int mid = (ss+se)/2;
	if (ai <= mid) rv(ai, val , ss, mid, si*2+1);
	else rv(ai, val, mid+1, se, si*2+2);
	seg[si] = delt[si] + max(seg[si*2+1], seg[si*2+2]);

}

void remval(int ai, int val) {
	rv(ai, val, 0, N+Q, 0);
}

void ta(int ts, int te, int diff, int ss, int se, int si) {
	if (ts > te || ss > se) return;
	if (ts > se || te < ss) return;
	if (ts <= ss && se <= te) {
		// cout << "tagging " << ss << " to " << se << " with: " << diff << endl;
		delt[si] += diff;
		seg[si]  += diff;
		return;
	}
	int mid = (ss+se)/2;
	ta(ts, te, diff, ss, mid, si*2+1);
	ta(ts, te, diff, mid+1, se, si*2+2);
	seg[si] = delt[si] + max(seg[si*2+1], seg[si*2+2]);
}

void tag(int ts, int te, int diff) {
	// cout << "told to tag: " << ts << " to " << te << " with " << diff << endl;
	ta(ts, te, diff, 0, N+Q, 0);
}

vector<int> countScans(vector<int> A,vector<int> X, vector<int> V){

	fill(seg, seg+maxn*4, -12438); //random numbers

	Q = X.size();
	N = A.size();

	set<int> nums;
	int ct = 0;
	for (int val : A) nums.insert(val);
	for (int val : V) nums.insert(val);

	for (int val : nums) {
		dec[val] = ct++;
		// cout << "dec stuff: " << ct-1 << " goes to " << val << endl;
	}

	for (int i = 0; i < N; i++) {
		A[i] = dec[A[i]];
		cvals[i] = A[i];
	}

	for (int i = 0; i < Q; i++) {
		V[i] = dec[V[i]];
	}

	vector<int> onums;
	for (int val : A) onums.push_back(val);
	sort(onums.begin(), onums.end());
	// cout << "onums: ";
	// for (int val : onums) cout << val << " ";
	// cout << endl;

	for (int i = 0; i < maxn; i++) {

		ovals[i] = upper_bound(onums.begin(), onums.end(), i)-onums.begin();
		// if (i <= 5) cout << i << ": " << ovals[i] << endl;
	}


	for (int i = 0; i < N; i++) {
		addval(A[i], i-ovals[A[i]]+1);
	}

	vector<int> answer(Q);
	for (int i = 0; i < Q; i++) {
		// cout << "doing: " << i << endl << endl;
		int ci = X[i];
		int vi = V[i];
		int ov = cvals[ci];

		cvals[ci] = vi;
		remval(ov, ci-ovals[ov]+1);
		addval(vi, ci-ovals[vi]+1);
		tag(vi, N+Q, -1);
		tag(ov, N+Q, 1);



		answer[i] = query();
	}
	return answer;
	
}

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