Submission #467867

#	Time	Username	Problem	Language	Result	Execution time	Memory
467867		kingfran1907	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2302 ms	45832 KiB

bubblesort2

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

using namespace std;
typedef long long llint;

const int maxn = 1e6+10;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;
const int inf = 0x3f3f3f3f;

int n, q;
int tour[treesiz], prop[treesiz];
vector< pair<int, int> > v;

void send(int x) {
	tour[x * 2] += prop[x];
	tour[x * 2 + 1] += prop[x];
	
	prop[x * 2] += prop[x];
	prop[x * 2 + 1] += prop[x];
	prop[x] = 0;
}

void update(int a, int b, int l, int r, int node, int val) {
	if (l > b || r < a) return;
	if (l >= a && r <= b) {
		tour[node] += val;
		prop[node] += val;
		return;
	}
	
	int mid = (l + r) / 2;
	send(node);
	
	update(a, b, l, mid, node * 2, val);
	update(a, b, mid + 1, r, node * 2 + 1, val);
	tour[node] = max(tour[node * 2], tour[node * 2 + 1]);
}

int query(int a, int b, int l, int r, int node) {
	if (l > b || r < a) return -inf;
	if (l >= a && r <= b) return tour[node];
	
	int mid = (l + r) / 2;
	send(node);
	return max(query(a, b, l, mid, node * 2), query(a, b, mid + 1, r, node * 2 + 1));
}

vector<int> countScans(vector<int> a, vector<int> x, vector<int> vs){
	n = a.size();
	q = x.size();
	vector< int > ans;
	
	for (int i = 0; i < n; i++) {
		v.push_back(make_pair(a[i], i));
	}
	for (int i = 0; i < q; i++) {
		v.push_back(make_pair(vs[i], x[i]));
	}
	
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	for (int i = 0; i < n; i++) 
		a[i] = lower_bound(v.begin(), v.end(), make_pair(a[i], i)) - v.begin();
		
	update(0, off - 1, 0, off - 1, 1, -inf);
	for (int i = 0; i < n; i++) {
		update(a[i], a[i], 0, off - 1, 1, inf + i);
		update(a[i] + 1, off - 1, 0, off - 1,  1, -1);
	}
		
	for (int i = 0; i < q; i++) {
		int ind = x[i];
		update(a[ind], a[ind], 0, off - 1, 1, -inf - ind);
		update(a[ind] + 1, off - 1, 0, off - 1, 1, 1);
		
		a[ind] = lower_bound(v.begin(), v.end(), make_pair(vs[i], x[i])) - v.begin();
		update(a[ind], a[ind], 0, off - 1, 1, inf + ind);
		update(a[ind] + 1, off - 1, 0, off - 1, 1, -1);
		
		ans.push_back(query(0, off - 1, 0, off - 1, 1));
	}
	return ans;
}

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