Submission #641511

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
641511	2022-09-16T20:34:53 Z	IWTIM	Bubble Sort 2 (JOI18_bubblesort2)	C++17	60 / 100	594 ms	69672 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 = 5e5+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	2 ms	468 KB	Output is correct
3	Correct	5 ms	596 KB	Output is correct
4	Correct	5 ms	576 KB	Output is correct
5	Correct	5 ms	596 KB	Output is correct
6	Correct	5 ms	580 KB	Output is correct
7	Correct	5 ms	596 KB	Output is correct
8	Correct	5 ms	688 KB	Output is correct
9	Correct	5 ms	596 KB	Output is correct
10	Correct	4 ms	596 KB	Output is correct
11	Correct	4 ms	596 KB	Output is correct
12	Correct	5 ms	596 KB	Output is correct
13	Correct	4 ms	596 KB	Output is correct
14	Correct	5 ms	596 KB	Output is correct
15	Correct	5 ms	612 KB	Output is correct
16	Correct	4 ms	596 KB	Output is correct
17	Correct	4 ms	596 KB	Output is correct
18	Correct	4 ms	596 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	2 ms	468 KB	Output is correct
3	Correct	5 ms	596 KB	Output is correct
4	Correct	5 ms	576 KB	Output is correct
5	Correct	5 ms	596 KB	Output is correct
6	Correct	5 ms	580 KB	Output is correct
7	Correct	5 ms	596 KB	Output is correct
8	Correct	5 ms	688 KB	Output is correct
9	Correct	5 ms	596 KB	Output is correct
10	Correct	4 ms	596 KB	Output is correct
11	Correct	4 ms	596 KB	Output is correct
12	Correct	5 ms	596 KB	Output is correct
13	Correct	4 ms	596 KB	Output is correct
14	Correct	5 ms	596 KB	Output is correct
15	Correct	5 ms	612 KB	Output is correct
16	Correct	4 ms	596 KB	Output is correct
17	Correct	4 ms	596 KB	Output is correct
18	Correct	4 ms	596 KB	Output is correct
19	Correct	22 ms	1436 KB	Output is correct
20	Correct	19 ms	1504 KB	Output is correct
21	Correct	19 ms	1472 KB	Output is correct
22	Correct	20 ms	1492 KB	Output is correct
23	Correct	18 ms	1452 KB	Output is correct
24	Correct	18 ms	1492 KB	Output is correct
25	Correct	21 ms	1492 KB	Output is correct
26	Correct	18 ms	1480 KB	Output is correct
27	Correct	17 ms	1476 KB	Output is correct
28	Correct	18 ms	1472 KB	Output is correct

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	2000 KB	Output is correct
2	Correct	77 ms	4036 KB	Output is correct
3	Correct	138 ms	6724 KB	Output is correct
4	Correct	136 ms	6616 KB	Output is correct
5	Correct	143 ms	6720 KB	Output is correct
6	Correct	139 ms	6592 KB	Output is correct
7	Correct	147 ms	6632 KB	Output is correct
8	Correct	136 ms	6592 KB	Output is correct
9	Correct	137 ms	6592 KB	Output is correct
10	Correct	99 ms	5064 KB	Output is correct
11	Correct	105 ms	5108 KB	Output is correct
12	Correct	96 ms	5092 KB	Output is correct
13	Correct	99 ms	5052 KB	Output is correct
14	Correct	97 ms	5136 KB	Output is correct
15	Correct	99 ms	5076 KB	Output is correct
16	Correct	95 ms	4672 KB	Output is correct
17	Correct	96 ms	4740 KB	Output is correct
18	Correct	95 ms	4696 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	2 ms	468 KB	Output is correct
3	Correct	5 ms	596 KB	Output is correct
4	Correct	5 ms	576 KB	Output is correct
5	Correct	5 ms	596 KB	Output is correct
6	Correct	5 ms	580 KB	Output is correct
7	Correct	5 ms	596 KB	Output is correct
8	Correct	5 ms	688 KB	Output is correct
9	Correct	5 ms	596 KB	Output is correct
10	Correct	4 ms	596 KB	Output is correct
11	Correct	4 ms	596 KB	Output is correct
12	Correct	5 ms	596 KB	Output is correct
13	Correct	4 ms	596 KB	Output is correct
14	Correct	5 ms	596 KB	Output is correct
15	Correct	5 ms	612 KB	Output is correct
16	Correct	4 ms	596 KB	Output is correct
17	Correct	4 ms	596 KB	Output is correct
18	Correct	4 ms	596 KB	Output is correct
19	Correct	22 ms	1436 KB	Output is correct
20	Correct	19 ms	1504 KB	Output is correct
21	Correct	19 ms	1472 KB	Output is correct
22	Correct	20 ms	1492 KB	Output is correct
23	Correct	18 ms	1452 KB	Output is correct
24	Correct	18 ms	1492 KB	Output is correct
25	Correct	21 ms	1492 KB	Output is correct
26	Correct	18 ms	1480 KB	Output is correct
27	Correct	17 ms	1476 KB	Output is correct
28	Correct	18 ms	1472 KB	Output is correct
29	Correct	23 ms	2000 KB	Output is correct
30	Correct	77 ms	4036 KB	Output is correct
31	Correct	138 ms	6724 KB	Output is correct
32	Correct	136 ms	6616 KB	Output is correct
33	Correct	143 ms	6720 KB	Output is correct
34	Correct	139 ms	6592 KB	Output is correct
35	Correct	147 ms	6632 KB	Output is correct
36	Correct	136 ms	6592 KB	Output is correct
37	Correct	137 ms	6592 KB	Output is correct
38	Correct	99 ms	5064 KB	Output is correct
39	Correct	105 ms	5108 KB	Output is correct
40	Correct	96 ms	5092 KB	Output is correct
41	Correct	99 ms	5052 KB	Output is correct
42	Correct	97 ms	5136 KB	Output is correct
43	Correct	99 ms	5076 KB	Output is correct
44	Correct	95 ms	4672 KB	Output is correct
45	Correct	96 ms	4740 KB	Output is correct
46	Correct	95 ms	4696 KB	Output is correct
47	Correct	519 ms	21460 KB	Output is correct
48	Runtime error	594 ms	69672 KB	Execution killed with signal 11
49	Halted	0 ms	0 KB	-