oj.uz

Submission #963426

# Submission time Handle Problem Language Result Execution time Memory
963426 2024-04-15T01:59:48 Z Pring Bubble Sort 2 (JOI18_bubblesort2) C++17
100 / 100
 4448 ms 76388 KB 
#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);
			if (k == 0) return mp(0, rt);
			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].pri);
	}

	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;
	}
}

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);
		// FOR(j, 1, n + 1) debug(j, nd[j]);
	}
	// for (auto &i : ans) assert(i >= 0);
	return ans;
}

Compilation message

bubblesort2.cpp:141:10: warning: 'std::ostream& operator<<(std::ostream&, {anonymous}::TREAP::NODE)' defined but not used [-Wunused-function]
  141 | ostream &operator<<(ostream &ss, TREAP::NODE a) {
      |          ^~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14168 KB Output is correct
2 Correct 9 ms 14172 KB Output is correct
3 Correct 12 ms 14172 KB Output is correct
4 Correct 11 ms 14168 KB Output is correct
5 Correct 10 ms 14172 KB Output is correct
6 Correct 10 ms 14172 KB Output is correct
7 Correct 10 ms 14168 KB Output is correct
8 Correct 10 ms 14172 KB Output is correct
9 Correct 10 ms 14172 KB Output is correct
10 Correct 11 ms 14172 KB Output is correct
11 Correct 12 ms 14428 KB Output is correct
12 Correct 10 ms 14172 KB Output is correct
13 Correct 10 ms 14168 KB Output is correct
14 Correct 10 ms 14172 KB Output is correct
15 Correct 10 ms 14172 KB Output is correct
16 Correct 10 ms 14172 KB Output is correct
17 Correct 10 ms 14332 KB Output is correct
18 Correct 10 ms 14168 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14168 KB Output is correct
2 Correct 9 ms 14172 KB Output is correct
3 Correct 12 ms 14172 KB Output is correct
4 Correct 11 ms 14168 KB Output is correct
5 Correct 10 ms 14172 KB Output is correct
6 Correct 10 ms 14172 KB Output is correct
7 Correct 10 ms 14168 KB Output is correct
8 Correct 10 ms 14172 KB Output is correct
9 Correct 10 ms 14172 KB Output is correct
10 Correct 11 ms 14172 KB Output is correct
11 Correct 12 ms 14428 KB Output is correct
12 Correct 10 ms 14172 KB Output is correct
13 Correct 10 ms 14168 KB Output is correct
14 Correct 10 ms 14172 KB Output is correct
15 Correct 10 ms 14172 KB Output is correct
16 Correct 10 ms 14172 KB Output is correct
17 Correct 10 ms 14332 KB Output is correct
18 Correct 10 ms 14168 KB Output is correct
19 Correct 26 ms 14684 KB Output is correct
20 Correct 27 ms 14940 KB Output is correct
21 Correct 26 ms 14916 KB Output is correct
22 Correct 29 ms 15188 KB Output is correct
23 Correct 25 ms 14920 KB Output is correct
24 Correct 25 ms 14916 KB Output is correct
25 Correct 24 ms 14940 KB Output is correct
26 Correct 31 ms 14928 KB Output is correct
27 Correct 25 ms 14940 KB Output is correct
28 Correct 25 ms 14936 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 16336 KB Output is correct
2 Correct 107 ms 17868 KB Output is correct
3 Correct 188 ms 19520 KB Output is correct
4 Correct 192 ms 19540 KB Output is correct
5 Correct 181 ms 19688 KB Output is correct
6 Correct 191 ms 19528 KB Output is correct
7 Correct 178 ms 19548 KB Output is correct
8 Correct 204 ms 19640 KB Output is correct
9 Correct 183 ms 19636 KB Output is correct
10 Correct 120 ms 19576 KB Output is correct
11 Correct 125 ms 19664 KB Output is correct
12 Correct 132 ms 19584 KB Output is correct
13 Correct 141 ms 19660 KB Output is correct
14 Correct 138 ms 19656 KB Output is correct
15 Correct 136 ms 19580 KB Output is correct
16 Correct 136 ms 19604 KB Output is correct
17 Correct 147 ms 19656 KB Output is correct
18 Correct 141 ms 19660 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14168 KB Output is correct
2 Correct 9 ms 14172 KB Output is correct
3 Correct 12 ms 14172 KB Output is correct
4 Correct 11 ms 14168 KB Output is correct
5 Correct 10 ms 14172 KB Output is correct
6 Correct 10 ms 14172 KB Output is correct
7 Correct 10 ms 14168 KB Output is correct
8 Correct 10 ms 14172 KB Output is correct
9 Correct 10 ms 14172 KB Output is correct
10 Correct 11 ms 14172 KB Output is correct
11 Correct 12 ms 14428 KB Output is correct
12 Correct 10 ms 14172 KB Output is correct
13 Correct 10 ms 14168 KB Output is correct
14 Correct 10 ms 14172 KB Output is correct
15 Correct 10 ms 14172 KB Output is correct
16 Correct 10 ms 14172 KB Output is correct
17 Correct 10 ms 14332 KB Output is correct
18 Correct 10 ms 14168 KB Output is correct
19 Correct 26 ms 14684 KB Output is correct
20 Correct 27 ms 14940 KB Output is correct
21 Correct 26 ms 14916 KB Output is correct
22 Correct 29 ms 15188 KB Output is correct
23 Correct 25 ms 14920 KB Output is correct
24 Correct 25 ms 14916 KB Output is correct
25 Correct 24 ms 14940 KB Output is correct
26 Correct 31 ms 14928 KB Output is correct
27 Correct 25 ms 14940 KB Output is correct
28 Correct 25 ms 14936 KB Output is correct
29 Correct 36 ms 16336 KB Output is correct
30 Correct 107 ms 17868 KB Output is correct
31 Correct 188 ms 19520 KB Output is correct
32 Correct 192 ms 19540 KB Output is correct
33 Correct 181 ms 19688 KB Output is correct
34 Correct 191 ms 19528 KB Output is correct
35 Correct 178 ms 19548 KB Output is correct
36 Correct 204 ms 19640 KB Output is correct
37 Correct 183 ms 19636 KB Output is correct
38 Correct 120 ms 19576 KB Output is correct
39 Correct 125 ms 19664 KB Output is correct
40 Correct 132 ms 19584 KB Output is correct
41 Correct 141 ms 19660 KB Output is correct
42 Correct 138 ms 19656 KB Output is correct
43 Correct 136 ms 19580 KB Output is correct
44 Correct 136 ms 19604 KB Output is correct
45 Correct 147 ms 19656 KB Output is correct
46 Correct 141 ms 19660 KB Output is correct
47 Correct 788 ms 33452 KB Output is correct
48 Correct 3574 ms 69292 KB Output is correct
49 Correct 4070 ms 76164 KB Output is correct
50 Correct 4247 ms 75892 KB Output is correct
51 Correct 4377 ms 76016 KB Output is correct
52 Correct 4448 ms 75852 KB Output is correct
53 Correct 4197 ms 76000 KB Output is correct
54 Correct 3860 ms 76204 KB Output is correct
55 Correct 4062 ms 76216 KB Output is correct
56 Correct 3995 ms 76008 KB Output is correct
57 Correct 4035 ms 76388 KB Output is correct
58 Correct 3751 ms 76160 KB Output is correct
59 Correct 3435 ms 75408 KB Output is correct
60 Correct 3410 ms 74720 KB Output is correct
61 Correct 3502 ms 74684 KB Output is correct
62 Correct 3422 ms 74932 KB Output is correct
63 Correct 3259 ms 74808 KB Output is correct
64 Correct 3402 ms 74508 KB Output is correct
65 Correct 3329 ms 74520 KB Output is correct
66 Correct 3137 ms 74428 KB Output is correct
67 Correct 3148 ms 74520 KB Output is correct