Submission #641510

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
641510	2022-09-16T20:33:44 Z	IWTIM	Bubble Sort 2 (JOI18_bubblesort2)	C++17	60 / 100	521 ms	57812 KB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double; // or double, if TL is tight
using str = string; // yay python! 
 
// pairs
using pii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
#define mp make_pair
#define f first
#define s second
 
#define tcT template<class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 
using vi = V<int>;
using vb = V<bool>;
using vd = V<db>;
using vs = V<str>;
using vpi = V<pii>;
using vpl = V<pl>;
using vpd = V<pd>;
 
// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()
 
#define lb lower_bound
#define ub upper_bound
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
const int MOD = 998244353;
const int N = 3e5+5;
const ll inf = 1e9; // not too close to LLONG_MAX
const db PI = acos((db)-1);
const int dx[4]{1,0,-1,0}, dy[4]{0,1,0,-1}; // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
struct DSU {
	vi e; void init(int N) { e = vi(N,-1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } 
	bool sameSet(int a, int b) { return get(a) == get(b); }
	int size(int x) { return -e[get(x)]; }
	bool unite(int x, int y) { // union by size
		x = get(x), y = get(y); if (x == y) return 0;
		if (e[x] > e[y]) swap(x,y);
		e[x] += e[y]; e[y] = x; return 1;
	}
};
/*
inline namespace Helpers {
	//////////// is_iterable
	// https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable
	// this gets used only when we can call begin() and end() on that type
	tcT, class = void> struct is_iterable : false_type {};
	tcT> struct is_iterable<T, void_t<decltype(begin(declval<T>())),
	                                  decltype(end(declval<T>()))
	                                 >
	                       > : true_type {};
	tcT> constexpr bool is_iterable_v = is_iterable<T>::value;
 
	//////////// is_readable
	tcT, class = void> struct is_readable : false_type {};
	tcT> struct is_readable<T,
	        typename std::enable_if_t<
	            is_same_v<decltype(cin >> declval<T&>()), istream&>
	        >
	    > : true_type {};
	tcT> constexpr bool is_readable_v = is_readable<T>::value;
 
	//////////// is_printable
	// // https://nafe.es/posts/2020-02-29-is-printable/
	tcT, class = void> struct is_printable : false_type {};
	tcT> struct is_printable<T,
	        typename std::enable_if_t<
	            is_same_v<decltype(cout << declval<T>()), ostream&>
	        >
	    > : true_type {};
	tcT> constexpr bool is_printable_v = is_printable<T>::value;
}*/
using ll = long long;
using db = long double; // or double, if TL is tight
using str = string; // yay python! 
 
// pairs
using pii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
#define mp make_pair
#define f first
#define s second
 
#define tcT template<class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 
using vi = V<int>;
using vb = V<bool>;
using vd = V<db>;
using vs = V<str>;
using vpi = V<pii>;
using vpl = V<pl>;
using vpd = V<pd>;
 
// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()
 
#define lb lower_bound
#define ub upper_bound
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
 
/*
inline namespace Helpers {
	//////////// is_iterable
	// https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable
	// this gets used only when we can call begin() and end() on that type
	tcT, class = void> struct is_iterable : false_type {};
	tcT> struct is_iterable<T, void_t<decltype(begin(declval<T>())),
	                                  decltype(end(declval<T>()))
	                                 >
	                       > : true_type {};
	tcT> constexpr bool is_iterable_v = is_iterable<T>::value;
 
	//////////// is_readable
	tcT, class = void> struct is_readable : false_type {};
	tcT> struct is_readable<T,
	        typename std::enable_if_t<
	            is_same_v<decltype(cin >> declval<T&>()), istream&>
	        >
	    > : true_type {};
	tcT> constexpr bool is_readable_v = is_readable<T>::value;
 
	//////////// is_printable
	// // https://nafe.es/posts/2020-02-29-is-printable/
	tcT, class = void> struct is_printable : false_type {};
	tcT> struct is_printable<T,
	        typename std::enable_if_t<
	            is_same_v<decltype(cout << declval<T>()), ostream&>
	        >
	    > : true_type {};
	tcT> constexpr bool is_printable_v = is_printable<T>::value;
}*/
int n, q, treef[N], id[N], idx[N], a[N], vl[N], val[N];
int tree[4 *N], save[4 *N];
vector<pii> v;
int merge(int a, int b)
{
	return max(a, b);
}

void pull(int node, int le, int ri)
{
	if (!save[node]) return;
	tree[node] += save[node];
	if (le != ri)
	{
		save[2 *node] += save[node];
		save[2 *node + 1] += save[node];
	}

	save[node] = 0;
}

void assign(int node, int le, int ri, int start, int end, int val)
{
	pull(node, le, ri);
	if (le > end || ri < start) return;
	if (le >= start && ri <= end)
	{
		tree[node] = val;
		return;
	}

	int mid = (le + ri) / 2;
	assign(2 *node, le, mid, start, end, val);
	assign(2 *node + 1, mid + 1, ri, start, end, val);
	tree[node] = merge(tree[2 *node], tree[2 *node + 1]);
}

void add(int node, int le, int ri, int start, int end, int val)
{
	pull(node, le, ri);
	if (le > end || ri < start) return;
	if (le >= start && ri <= end)
	{
		save[node] += val;
		pull(node, le, ri);
		return;
	}

	int mid = (le + ri) / 2;
	add(2 *node, le, mid, start, end, val);
	add(2 *node + 1, mid + 1, ri, start, end, val);
	tree[node] = merge(tree[2 *node], tree[2 *node + 1]);
}

int getans(int node, int le, int ri, int start, int end)
{
	pull(node, le, ri);
	if (le > end || ri < start) return -inf;
	if (le >= start && ri <= end)
	{
		return tree[node];
	}

	int mid = (le + ri) / 2;
	return merge(getans(2 *node, le, mid, start, end), getans(2 *node + 1, mid + 1, ri, start, end));
}

void updatef(int idx, int val)
{
	for (int i = idx; i < N; i += i &(-i))
	{
		treef[i] += val;
	}
}

int getf(int idx)
{
	int pas = 0;
	for (int i = idx; i > 0; i -= i &(-i))
	{
		pas += treef[i];
	}

	return pas;
}

int getpos(pii x)
{
	return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector< int > V)
{
	q = X.size();
	n = A.size();
	for (int i = 1; i <= n; i++)
	{
		a[i] = A[i - 1];
		v.pb({ a[i], i });
	}

	for (int i = 0; i < q; i++)
	{
		idx[i] = X[i] + 1;
		vl[i] = V[i];
		v.pb({ vl[i], idx[i] });
	}

	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	int sz = v.size();
	for (int i = 1; i <= n; i++)
	{
		updatef(getpos({ a[i], i }), 1);
		id[getpos({ a[i], i })] = i;
	}

	for (int i = 0; i < v.size(); i++)
	{
		int sth = getpos({ v[i].f, v[i].s });
		if (id[sth]) val[i] = v[i].s - getf(getpos({ a[id[sth]], id[sth] }) - 1);
		else val[i] = -inf;
		assign(1, 1, sz, sth, sth, val[i]);
	}

	vector<int> answer;
	for (int i = 0; i < q; i++)
	{
		int now = getpos({ a[idx[i]], idx[i] });
		a[idx[i]] = vl[i];
		int nxt = getpos({ a[idx[i]], idx[i] });
		if (now <= nxt)
		{
			add(1, 1, sz, now, nxt, 1);
			updatef(now, -1);
			updatef(nxt, 1);
			assign(1, 1, sz, now, now, -1e9);
			assign(1, 1, sz, nxt, nxt, idx[i] - getf(nxt - 1));

		}
		else
		{
			// nxt < now
			add(1, 1, sz, nxt, now, -1);
			updatef(now, -1);
			updatef(nxt, 1);
			assign(1, 1, sz, now, now, -1e9);
			assign(1, 1, sz, nxt, nxt, idx[i] - getf(nxt - 1));
		}

		answer.pb(max(0, tree[1] - 1));
	}

	return answer;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:297:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  297 |  for (int i = 0; i < v.size(); i++)
      |                  ~~^~~~~~~~~~

Subtask #1

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	468 KB	Output is correct
2	Correct	3 ms	468 KB	Output is correct
3	Correct	6 ms	724 KB	Output is correct
4	Correct	5 ms	596 KB	Output is correct
5	Correct	5 ms	580 KB	Output is correct
6	Correct	4 ms	596 KB	Output is correct
7	Correct	4 ms	572 KB	Output is correct
8	Correct	5 ms	596 KB	Output is correct
9	Correct	5 ms	616 KB	Output is correct
10	Correct	5 ms	580 KB	Output is correct
11	Correct	4 ms	596 KB	Output is correct
12	Correct	4 ms	580 KB	Output is correct
13	Correct	4 ms	580 KB	Output is correct
14	Correct	4 ms	588 KB	Output is correct
15	Correct	4 ms	580 KB	Output is correct
16	Correct	4 ms	608 KB	Output is correct
17	Correct	4 ms	596 KB	Output is correct
18	Correct	4 ms	580 KB	Output is correct

Subtask #2

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	468 KB	Output is correct
2	Correct	3 ms	468 KB	Output is correct
3	Correct	6 ms	724 KB	Output is correct
4	Correct	5 ms	596 KB	Output is correct
5	Correct	5 ms	580 KB	Output is correct
6	Correct	4 ms	596 KB	Output is correct
7	Correct	4 ms	572 KB	Output is correct
8	Correct	5 ms	596 KB	Output is correct
9	Correct	5 ms	616 KB	Output is correct
10	Correct	5 ms	580 KB	Output is correct
11	Correct	4 ms	596 KB	Output is correct
12	Correct	4 ms	580 KB	Output is correct
13	Correct	4 ms	580 KB	Output is correct
14	Correct	4 ms	588 KB	Output is correct
15	Correct	4 ms	580 KB	Output is correct
16	Correct	4 ms	608 KB	Output is correct
17	Correct	4 ms	596 KB	Output is correct
18	Correct	4 ms	580 KB	Output is correct
19	Correct	17 ms	1364 KB	Output is correct
20	Correct	20 ms	1492 KB	Output is correct
21	Correct	19 ms	1472 KB	Output is correct
22	Correct	20 ms	1536 KB	Output is correct
23	Correct	18 ms	1496 KB	Output is correct
24	Correct	18 ms	1392 KB	Output is correct
25	Correct	18 ms	1492 KB	Output is correct
26	Correct	19 ms	1476 KB	Output is correct
27	Correct	17 ms	1460 KB	Output is correct
28	Correct	16 ms	1472 KB	Output is correct

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	2060 KB	Output is correct
2	Correct	81 ms	4176 KB	Output is correct
3	Correct	137 ms	7104 KB	Output is correct
4	Correct	139 ms	7056 KB	Output is correct
5	Correct	141 ms	7152 KB	Output is correct
6	Correct	140 ms	7116 KB	Output is correct
7	Correct	135 ms	7104 KB	Output is correct
8	Correct	133 ms	7104 KB	Output is correct
9	Correct	137 ms	7040 KB	Output is correct
10	Correct	103 ms	5740 KB	Output is correct
11	Correct	95 ms	5668 KB	Output is correct
12	Correct	99 ms	5596 KB	Output is correct
13	Correct	98 ms	5552 KB	Output is correct
14	Correct	101 ms	5704 KB	Output is correct
15	Correct	95 ms	5616 KB	Output is correct
16	Correct	99 ms	5112 KB	Output is correct
17	Correct	98 ms	5168 KB	Output is correct
18	Correct	97 ms	5184 KB	Output is correct

Subtask #4

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	468 KB	Output is correct
2	Correct	3 ms	468 KB	Output is correct
3	Correct	6 ms	724 KB	Output is correct
4	Correct	5 ms	596 KB	Output is correct
5	Correct	5 ms	580 KB	Output is correct
6	Correct	4 ms	596 KB	Output is correct
7	Correct	4 ms	572 KB	Output is correct
8	Correct	5 ms	596 KB	Output is correct
9	Correct	5 ms	616 KB	Output is correct
10	Correct	5 ms	580 KB	Output is correct
11	Correct	4 ms	596 KB	Output is correct
12	Correct	4 ms	580 KB	Output is correct
13	Correct	4 ms	580 KB	Output is correct
14	Correct	4 ms	588 KB	Output is correct
15	Correct	4 ms	580 KB	Output is correct
16	Correct	4 ms	608 KB	Output is correct
17	Correct	4 ms	596 KB	Output is correct
18	Correct	4 ms	580 KB	Output is correct
19	Correct	17 ms	1364 KB	Output is correct
20	Correct	20 ms	1492 KB	Output is correct
21	Correct	19 ms	1472 KB	Output is correct
22	Correct	20 ms	1536 KB	Output is correct
23	Correct	18 ms	1496 KB	Output is correct
24	Correct	18 ms	1392 KB	Output is correct
25	Correct	18 ms	1492 KB	Output is correct
26	Correct	19 ms	1476 KB	Output is correct
27	Correct	17 ms	1460 KB	Output is correct
28	Correct	16 ms	1472 KB	Output is correct
29	Correct	23 ms	2060 KB	Output is correct
30	Correct	81 ms	4176 KB	Output is correct
31	Correct	137 ms	7104 KB	Output is correct
32	Correct	139 ms	7056 KB	Output is correct
33	Correct	141 ms	7152 KB	Output is correct
34	Correct	140 ms	7116 KB	Output is correct
35	Correct	135 ms	7104 KB	Output is correct
36	Correct	133 ms	7104 KB	Output is correct
37	Correct	137 ms	7040 KB	Output is correct
38	Correct	103 ms	5740 KB	Output is correct
39	Correct	95 ms	5668 KB	Output is correct
40	Correct	99 ms	5596 KB	Output is correct
41	Correct	98 ms	5552 KB	Output is correct
42	Correct	101 ms	5704 KB	Output is correct
43	Correct	95 ms	5616 KB	Output is correct
44	Correct	99 ms	5112 KB	Output is correct
45	Correct	98 ms	5168 KB	Output is correct
46	Correct	97 ms	5184 KB	Output is correct
47	Correct	521 ms	24820 KB	Output is correct
48	Runtime error	261 ms	57812 KB	Execution killed with signal 11
49	Halted	0 ms	0 KB	-