Submission #776746

#	Time	Username	Problem	Language	Result	Execution time	Memory
776746		NothingXD	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	2710 ms	163544 KiB

bubblesort2

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

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cout << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__);
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 5e5 + 10;

int n, q, sz, seg[maxn << 3], lazy[maxn << 3];
vector<int> num;
set<int> idx[maxn << 1];

void shift(int v, int l, int r);

void add(int v, int l, int r, int ql, int qr, int val){
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr){
		seg[v] += val;
		lazy[v] += val;
		return;
	}
	shift(v, l, r);
	int mid = (l + r)>> 1;
	add(v << 1, l, mid, ql, qr, val);
	add(v << 1 | 1, mid, r, ql, qr, val);
	seg[v] = max(seg[v << 1], seg[v << 1 | 1]);
}

void shift(int v, int l, int r){
	if (lazy[v] == 0) return;
	int mid = (l+r) >> 1;
	add(v << 1, l, mid, l, mid, lazy[v]);
	add(v << 1 | 1, mid, r, mid, r, lazy[v]);
	lazy[v] = 0;
}

void add(int x, int y){
	auto it = idx[y].end();
	it--;
	if (x > *it) add(1, 0, sz, y, y+1, x-(*it));
	add(1, 0, sz, y, sz, -1);
	idx[y].insert(x);
}

void remove(int x, int y){
	idx[y].erase(x);
	add(1, 0, sz, y, sz, 1);
	auto it = idx[y].end();
	it--;
	if (x > *it) add(1, 0, sz, y, y+1, -x+(*it));
}

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

	n = A.size();
	q = X.size();
	for (int i = 0; i < n; i++) num.push_back(A[i]);
	for (int i = 0; i < q; i++) num.push_back(V[i]);
	sort(all(num));
	num.resize(distance(num.begin(), unique(all(num))));

	sz = num.size();
	for (int i = 0; i < sz; i++) idx[i].insert(0);

	for (int i = 0; i < n; i++){
		A[i] = lower_bound(all(num), A[i]) - num.begin();
		add(i+1, A[i]);
	}

	vector<int> ans;

	for (int i = 0; i < q; i++){
		V[i] = lower_bound(all(num), V[i]) - num.begin();
		remove(X[i]+1, A[X[i]]);
		A[X[i]] = V[i];
		add(X[i]+1, A[X[i]]);
		ans.push_back(max(0, seg[1]));
	}
	return ans;
	
}

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