답안 #641512

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
641512	2022-09-16T20:36:17 Z	IWTIM	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	2230 ms	71180 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 = 1e6+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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 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	596 KB	Output is correct
5	Correct	5 ms	596 KB	Output is correct
6	Correct	4 ms	596 KB	Output is correct
7	Correct	5 ms	596 KB	Output is correct
8	Correct	4 ms	596 KB	Output is correct
9	Correct	5 ms	596 KB	Output is correct
10	Correct	5 ms	596 KB	Output is correct
11	Correct	5 ms	596 KB	Output is correct
12	Correct	4 ms	640 KB	Output is correct
13	Correct	4 ms	644 KB	Output is correct
14	Correct	4 ms	640 KB	Output is correct
15	Correct	4 ms	640 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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 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	596 KB	Output is correct
5	Correct	5 ms	596 KB	Output is correct
6	Correct	4 ms	596 KB	Output is correct
7	Correct	5 ms	596 KB	Output is correct
8	Correct	4 ms	596 KB	Output is correct
9	Correct	5 ms	596 KB	Output is correct
10	Correct	5 ms	596 KB	Output is correct
11	Correct	5 ms	596 KB	Output is correct
12	Correct	4 ms	640 KB	Output is correct
13	Correct	4 ms	644 KB	Output is correct
14	Correct	4 ms	640 KB	Output is correct
15	Correct	4 ms	640 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	17 ms	1316 KB	Output is correct
20	Correct	21 ms	1484 KB	Output is correct
21	Correct	19 ms	1376 KB	Output is correct
22	Correct	20 ms	1364 KB	Output is correct
23	Correct	18 ms	1364 KB	Output is correct
24	Correct	18 ms	1364 KB	Output is correct
25	Correct	17 ms	1360 KB	Output is correct
26	Correct	18 ms	1364 KB	Output is correct
27	Correct	17 ms	1292 KB	Output is correct
28	Correct	17 ms	1364 KB	Output is correct

Subtask #3

22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	1968 KB	Output is correct
2	Correct	80 ms	3916 KB	Output is correct
3	Correct	139 ms	6528 KB	Output is correct
4	Correct	153 ms	6588 KB	Output is correct
5	Correct	137 ms	6524 KB	Output is correct
6	Correct	142 ms	6468 KB	Output is correct
7	Correct	132 ms	6480 KB	Output is correct
8	Correct	141 ms	6572 KB	Output is correct
9	Correct	154 ms	6472 KB	Output is correct
10	Correct	101 ms	4940 KB	Output is correct
11	Correct	98 ms	5052 KB	Output is correct
12	Correct	98 ms	5044 KB	Output is correct
13	Correct	103 ms	5064 KB	Output is correct
14	Correct	99 ms	5028 KB	Output is correct
15	Correct	98 ms	4976 KB	Output is correct
16	Correct	100 ms	4572 KB	Output is correct
17	Correct	98 ms	4556 KB	Output is correct
18	Correct	96 ms	4552 KB	Output is correct

Subtask #4

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 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	596 KB	Output is correct
5	Correct	5 ms	596 KB	Output is correct
6	Correct	4 ms	596 KB	Output is correct
7	Correct	5 ms	596 KB	Output is correct
8	Correct	4 ms	596 KB	Output is correct
9	Correct	5 ms	596 KB	Output is correct
10	Correct	5 ms	596 KB	Output is correct
11	Correct	5 ms	596 KB	Output is correct
12	Correct	4 ms	640 KB	Output is correct
13	Correct	4 ms	644 KB	Output is correct
14	Correct	4 ms	640 KB	Output is correct
15	Correct	4 ms	640 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	17 ms	1316 KB	Output is correct
20	Correct	21 ms	1484 KB	Output is correct
21	Correct	19 ms	1376 KB	Output is correct
22	Correct	20 ms	1364 KB	Output is correct
23	Correct	18 ms	1364 KB	Output is correct
24	Correct	18 ms	1364 KB	Output is correct
25	Correct	17 ms	1360 KB	Output is correct
26	Correct	18 ms	1364 KB	Output is correct
27	Correct	17 ms	1292 KB	Output is correct
28	Correct	17 ms	1364 KB	Output is correct
29	Correct	23 ms	1968 KB	Output is correct
30	Correct	80 ms	3916 KB	Output is correct
31	Correct	139 ms	6528 KB	Output is correct
32	Correct	153 ms	6588 KB	Output is correct
33	Correct	137 ms	6524 KB	Output is correct
34	Correct	142 ms	6468 KB	Output is correct
35	Correct	132 ms	6480 KB	Output is correct
36	Correct	141 ms	6572 KB	Output is correct
37	Correct	154 ms	6472 KB	Output is correct
38	Correct	101 ms	4940 KB	Output is correct
39	Correct	98 ms	5052 KB	Output is correct
40	Correct	98 ms	5044 KB	Output is correct
41	Correct	103 ms	5064 KB	Output is correct
42	Correct	99 ms	5028 KB	Output is correct
43	Correct	98 ms	4976 KB	Output is correct
44	Correct	100 ms	4572 KB	Output is correct
45	Correct	98 ms	4556 KB	Output is correct
46	Correct	96 ms	4552 KB	Output is correct
47	Correct	553 ms	21208 KB	Output is correct
48	Correct	2045 ms	55128 KB	Output is correct
49	Correct	2201 ms	70840 KB	Output is correct
50	Correct	2230 ms	70892 KB	Output is correct
51	Correct	2205 ms	70748 KB	Output is correct
52	Correct	2163 ms	70800 KB	Output is correct
53	Correct	2178 ms	70824 KB	Output is correct
54	Correct	2056 ms	71000 KB	Output is correct
55	Correct	2169 ms	71052 KB	Output is correct
56	Correct	2101 ms	71180 KB	Output is correct
57	Correct	2138 ms	71032 KB	Output is correct
58	Correct	2150 ms	71092 KB	Output is correct
59	Correct	1845 ms	68308 KB	Output is correct
60	Correct	1876 ms	68152 KB	Output is correct
61	Correct	1877 ms	68372 KB	Output is correct
62	Correct	1760 ms	67296 KB	Output is correct
63	Correct	1756 ms	67368 KB	Output is correct
64	Correct	1772 ms	67368 KB	Output is correct
65	Correct	1595 ms	66652 KB	Output is correct
66	Correct	1606 ms	66448 KB	Output is correct
67	Correct	1604 ms	66572 KB	Output is correct