Submission #255619

#	Time	Username	Problem	Language	Result	Execution time	Memory
255619		Falcon	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	4099 ms	63796 KiB

bubblesort2

#pragma GCC optimize("O2")

#include <bits/stdc++.h>
#ifdef DEBUG
	#include "debug.hpp"
#endif

using namespace std;

#define all(c) (c).begin(), (c).end()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); it++)
#define rep(i, N) for(int i = 0; i < (N); i++)
#define rep1(i, N) for(int i = 1; i <= (N); i++)
#define rep2(i, s, e) for(int i = (s); i <= (e); i++)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back


#ifdef DEBUG
	#define debug(x...) {dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals);}
	#define light_debug(x) {dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << "  " << #x << " = " << x << endl; dbg::light = 0;}
#else
	#define debug(x...)
	#define light_debug(x) 
#endif


using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> uid(0, 1 << 30);

class Treap{

private:
	struct node{
		int v, i, prior, size, diff, dp;
		node* l; node* r;
		node(int _v, int _i){
			prior = uid(rng);
			v = _v;
			i = _i;
			dp = i;
			l = r = 0;
			size = 1;
		}
	};

	using pnode = node*;

	pnode root = 0;

	inline int size(pnode t){
		return t ? t->size : 0;
	}

	inline int dp(pnode t){
		return t ? t->dp : 0;
	}

	inline void pull(pnode t){
		if(t) {
			t->size = size(t->l) + 1 + size(t->r);
			t->dp = max(max(dp(t->l), dp(t->r) - size(t->l) - 1), t->i - size(t->l));
		}
	}

	void split(pnode t, pnode& l, pnode& r, int v, int i){
		if(!t)
			l = r = 0;
		else if(make_pair(t->v, t->i) <= make_pair(v, i))
			split(t->r, t->r, r, v, i), l = t;
		else
			split(t->l, l, t->l, v, i), r = t;
		pull(t);
	}

	void merge(pnode& t, pnode l, pnode r){
		if(!l || !r)
			t = l ? l : r;
		else if(l->prior >= r->prior)
			merge(l->r, l->r, r), t = l;
		else
			merge(r->l, l, r->l), t = r;
		pull(t);
	}

public:

	void insert(int i, int v){
		pnode l, m, r;
		split(root, m, r, v, i);
		split(m, l, m, v, i - 1);
		m = new node(v, i);
		merge(root, l, m);
		merge(root, root, r);
	}

	void erase(int i, int v){
		pnode l, m, r;
		split(root, m, r, v, i);
		split(m, l, m, v, i - 1);
		m = 0;
		merge(root, l, m);
		merge(root, root, r);
	}

	int query(){
		return root->dp;
	}
};


std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	int N = A.size(), Q = X.size();
	Treap trp;
	vector<int> answer(Q);
	rep(i, N) 
		trp.insert(i, A[i]);
	rep(i, Q){
		int x = X[i], v = V[i];
		trp.erase(x, A[x]);
		trp.insert(x, v);
		A[x] = v;
		answer[i] = trp.query();
	}
	return answer;
}

signed main1(){

	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	#ifdef DEBUG
		freopen("debug", "w", stderr);
	#endif

	int N, Q;
	Treap trp;
	vi A;
	 
	cin >> N >> Q;
	A.resize(N);
	rep(i, N) {
		cin >> A[i];
		trp.insert(i, A[i]);
	}

	debug(trp.query());

	while(Q--){
		int x, v;
		cin >> x >> v;
		trp.erase(x, A[x]);
		trp.insert(x, v);
		A[x] = v;
		cout << trp.query() << '\n';
	}

	#ifdef DEBUG
		dbg::dout << "\nExecution time: " << clock() << "ms\n";
	#endif

	return 0;
}

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