Submission #963422

#	Time	Username	Problem	Language	Result	Execution time	Memory
963422		Pring	Bubble Sort 2 (JOI18_bubblesort2)	C++17	38 / 100	9103 ms	18148 KiB

bubblesort2

#include <bits/stdc++.h>
#include <bits/extc++.h>
#include "bubblesort2.h"
using namespace std;
using namespace __gnu_pbds;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> TREE;

namespace {
	const int MXN = 500005;
	int n;
	vector<int> a;
	TREE MS;

	namespace TREAP {
		mt19937 rnd(time(nullptr));
		struct NODE {
			int l, r, pri, sz, val, big, tag;
			NODE(int v = 0) : l(0), r(0), pri(rnd()), sz(1), val(v), big(v), tag(0) {}
		} nd[MXN];
		int rt;
		
		void add_tag(int id, int _t) {
			if (id == 0) return;
			nd[id].val += _t;
			nd[id].big += _t;
			nd[id].tag += _t;
		}
		void PUSH(int id) {
			add_tag(nd[id].l, nd[id].tag);
			add_tag(nd[id].r, nd[id].tag);
			nd[id].tag = 0;
		}
		void PULL(int id) {
			nd[id].big = max({nd[nd[id].l].big, nd[nd[id].r].big, nd[id].val});
			nd[id].sz = nd[nd[id].l].sz + nd[nd[id].r].sz + 1;
		}
		int MERGE(int ta, int tb) {
			if (ta == 0) return tb;
			if (tb == 0) return ta;
			if (nd[ta].pri > nd[tb].pri) {
				PUSH(ta);
				nd[ta].r = MERGE(nd[ta].r, tb);
				PULL(ta);
				return ta;
			} else {
				PUSH(tb);
				nd[tb].l = MERGE(ta, nd[tb].l);
				PULL(tb);
				return tb;
			}
			return 0;
		}
		pii SPLIT(int rt, int k) {
			if (rt == 0) return mp(0, 0);
			int lsz = nd[nd[rt].l].sz + 1;
			PUSH(rt);
			if (lsz <= k) {
				auto [ta, tb] = SPLIT(nd[rt].r, k - lsz);
				nd[rt].r = ta;
				PULL(rt);
				return mp(rt, tb);
			} else {
				auto [ta, tb] = SPLIT(nd[rt].l, k);
				nd[rt].l = tb;
				PULL(rt);
				return mp(ta, rt);
			}
			return mp(0, 0);
		}
	}

	void INIT() {
		using namespace TREAP;
		nd[0] = NODE(-MXN);
		nd[0].sz = 0;
		vector<pii> dist;
		FOR(i, 0, n) dist.push_back(mp(a[i], i));
		sort(dist.begin(), dist.end());
		FOR(i, 0, n) MS.insert(dist[i]);
		FOR(i, 0, n) {
			nd[i + 1] = NODE(dist[i].sc - i);
		}
		rt = 1;
		FOR(i, 1, n) rt = MERGE(rt, i + 1);
		FOR(j, 1, n + 1) debug(j, nd[j]);
	}

	int SOLVE(int p, int v) {
		using namespace TREAP;
		int now = MS.order_of_key(mp(a[p], p));
		MS.erase(MS.find(mp(a[p], p)));
		int nxt = MS.order_of_key(mp(v, p));
		MS.insert(mp(v, p));
		a[p] = v;
		debug(now, nxt);
		if (now == nxt) return nd[rt].big;
		auto [ta, t1] = SPLIT(rt, min(now, nxt));
		auto [tt, td] = SPLIT(t1, abs(nxt - now) + 1);
		if (now > nxt) {
			auto [tb, tc] = SPLIT(tt, now - nxt);
			debug(ta, tb, tc, td);
			add_tag(tc, now - nxt);
			add_tag(tb, -1);
			tt = MERGE(tc, tb);
			t1 = MERGE(tt, td);
			rt = MERGE(ta, t1);
		} else {
			auto [tb, tc] = SPLIT(tt, 1);
			debug(ta, tb, tc, td, 2);
			add_tag(tb, now - nxt);
			add_tag(tc, 1);
			tt = MERGE(tc, tb);
			t1 = MERGE(tt, td);
			rt = MERGE(ta, t1);
		}
		return nd[rt].big;
	}

	void DFS(int id, int &C) {
		if (id == 0) return;
		using namespace TREAP;
		DFS(nd[id].l, C);
		debug(id, nd[id].val + C);
		C++;
		DFS(nd[id].r, C);
	}
}

ostream &operator<<(ostream &ss, TREAP::NODE a) {
	ss << '<' << a.val << ' ' << a.big << ' ' << a.tag << ' ' << a.sz << ' ' << a.l << ' ' << a.r << '>';
	return ss;
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
	::a = A;
	::n = A.size();
	int q = X.size();
	vector<int> ans;
	INIT();
	FOR(i, 0, q) {
		ans.push_back(SOLVE(X[i], V[i]));
		using namespace TREAP;
		debug(rt);
		int C = 0;
		DFS(rt, C);
		FOR(j, 1, n + 1) debug(j, nd[j]);
	}
	// for (auto &i : ans) assert(i >= 0);
	return ans;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'void {anonymous}::INIT()':
bubblesort2.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 39
      |                    ^~
bubblesort2.cpp:105:20: note: in expansion of macro 'debug'
  105 |   FOR(j, 1, n + 1) debug(j, nd[j]);
      |                    ^~~~~
bubblesort2.cpp: In function 'int {anonymous}::SOLVE(int, int)':
bubblesort2.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 39
      |                    ^~
bubblesort2.cpp:115:3: note: in expansion of macro 'debug'
  115 |   debug(now, nxt);
      |   ^~~~~
bubblesort2.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 39
      |                    ^~
bubblesort2.cpp:121:4: note: in expansion of macro 'debug'
  121 |    debug(ta, tb, tc, td);
      |    ^~~~~
bubblesort2.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 39
      |                    ^~
bubblesort2.cpp:129:4: note: in expansion of macro 'debug'
  129 |    debug(ta, tb, tc, td, 2);
      |    ^~~~~
bubblesort2.cpp: In function 'void {anonymous}::DFS(int, int&)':
bubblesort2.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 39
      |                    ^~
bubblesort2.cpp:143:3: note: in expansion of macro 'debug'
  143 |   debug(id, nd[id].val + C);
      |   ^~~~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 39
      |                    ^~
bubblesort2.cpp:163:3: note: in expansion of macro 'debug'
  163 |   debug(rt);
      |   ^~~~~
bubblesort2.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 39
      |                    ^~
bubblesort2.cpp:166:20: note: in expansion of macro 'debug'
  166 |   FOR(j, 1, n + 1) debug(j, nd[j]);
      |                    ^~~~~
bubblesort2.cpp: At global scope:
bubblesort2.cpp:149:10: warning: 'std::ostream& operator<<(std::ostream&, {anonymous}::TREAP::NODE)' defined but not used [-Wunused-function]
  149 | ostream &operator<<(ostream &ss, TREAP::NODE a) {
      |          ^~~~~~~~

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