Submission #61427

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
61427	2018-07-26T00:14:55 Z	qkxwsm	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	4378 ms	312060 KB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"

using namespace std;

template<class T>
void readi(T &x)
{
	T input = 0;
	bool negative = false;
	char c = ' ';
	while (c < '-')
	{
		c = getchar();
	}
	if (c == '-')
	{
		negative = true;
		c = getchar();
	}
	while (c >= '0')
	{
		input = input * 10 + (c - '0');
		c = getchar();
	}
	if (negative)
	{
		input = -input;
	}
	x = input;
}
template<class T>
void printi(T output)
{
	if (output == 0)
	{
		putchar('0');
		return;
	}
	if (output < 0)
	{
		putchar('-');
		output = -output;
	}
	int aout[20];
	int ilen = 0;
	while(output)
	{
		aout[ilen] = ((output % 10));
		output /= 10;
		ilen++;
	}
	for (int i = ilen - 1; i >= 0; i--)
	{
		putchar(aout[i] + '0');
	}
	return;
}
template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
long long randomize(long long mod)
{
	return ((1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}

#define MP make_pair
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-10;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 500013

long long normalize(long long x, long long mod = INF)
{
	return (((x % mod) + mod) % mod);
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

int N, Q, M;
int arr[MAXN], temp[MAXN];
pii quer[MAXN];
int ans[MAXN];
int pos0[2 * MAXN], pos1[2 * MAXN];
vector<ll> compress;
int seg[8 * MAXN], lazy[8 * MAXN];
int tree[2 * MAXN];

void ud(int idx, int val)
{
	for (int e = idx + 1; e <= M; e += e & (-e))
	{
		tree[e] += val;
	}
}
int get(int idx)
{
	int res = 0;
	for (int e = idx + 1; e > 0; e -= e & (-e))
	{
		res += tree[e];
	}
	return res;
}
void down(int w, int L, int R)
{
	seg[w] += lazy[w];
	if (L != R)
	{
		lazy[2 * w] += lazy[w];
		lazy[2 * w + 1] += lazy[w];
	}
	lazy[w] = 0;
	return;
}
void update(int w, int L, int R, int a, int b, int val)
{
//	cerr << "update " << a << '-' << b << " = " << val << endl;
	down(w, L, R);
	if (b < L || R < a)
	{
		return;
	}
	if (a <= L && R <= b)
	{
		lazy[w] += val;
		down(w, L, R);
		return;
	}
	int mid = (L + R)/2;
	update(2 * w, L, mid, a, b, val);
	update(2 * w + 1, mid + 1, R, a, b, val);
	seg[w] = max(seg[2 * w], seg[2 * w + 1]);
}
int query(int w, int L, int R, int a, int b)
{
	down(w, L, R);
	if (b < L || R < a)
	{
		return -INF;
	}
	if (a <= L && R <= b)
	{
		return seg[w];
	}
	int mid = (L + R)/2;
	return max(query(2 * w, L, mid, a, b), query(2 * w + 1, mid + 1, R, a, b));
}
void setval(int idx, int val)
{
	int was = query(1, 0, M - 1, idx, idx);
	update(1, 0, M - 1, idx, idx, val - was);
	return;
}
vi countScans(vi a, vi b, vi c)
{
	N = a.size();
	Q = b.size();
	for (int i = 0; i < N; i++)
	{
		arr[i] = a[i];
	}
	for (int i = 0; i < Q; i++)
	{
		quer[i] = MP(b[i], c[i]);
	}
	for (int i = 0; i < N; i++)
	{
		compress.PB(1ll * arr[i] * INF + i);
	}
	for (int i = 0; i < Q; i++)
	{
		compress.PB(1ll * quer[i].se * INF + quer[i].fi);
	}
	sort(compress.begin(), compress.end());
	compress.erase(unique(compress.begin(), compress.end()), compress.end());
	for (int i = 0; i < N; i++)
	{
		arr[i] = LB(compress.begin(), compress.end(), 1ll * arr[i] * INF + i) - compress.begin();
	}
	for (int i = 0; i < Q; i++)
	{
		quer[i].se = LB(compress.begin(), compress.end(), 1ll * quer[i].se * INF + quer[i].fi) - compress.begin();
	}
	//	for (int i = 0; i < N; i++)
	//	{
	//		cerr << arr[i] << ' ';
	//	}
	//	cerr << endl;
	//	for (int i = 0; i < Q; i++)
	//	{
	//		cerr << quer[i].fi << ' ' << quer[i].se << endl;
	//	}
	M = compress.size();
	update(1, 0, M - 1, 0, M - 1, -10 * CO);
	for (int i = 0; i < N; i++)
	{
		pos1[arr[i]] = i;
	}
	for (int i = 0; i < N; i++)
	{
		temp[i] = arr[i];
	}
	sort(temp, temp + N);
	for (int i = 0; i < N; i++)
	{
		pos0[temp[i]] = i;
	}
	for (int i = 0; i < N; i++)
	{
		setval(arr[i], pos1[arr[i]] - pos0[arr[i]]);
	}
	for (int i = 0; i < N; i++)
	{
		ud(arr[i], 1);
	}
	for (int q = 0; q < Q; q++)
	{
		//each guy with value > arr[idx] has to
		int idx = quer[q].fi, val = quer[q].se, was = arr[idx];
		arr[idx] = val;
		ud(was, -1);
		ud(val, 1);
//		pos1[was] = 0;
		setval(was, -10 * CO);
//		pos1[val] = idx;
		setval(val, idx);
		//the thing is, each guy only moves by at most one...
		//when you delete x, each guy moves down 1
//		for (int i = was + 1; i < M; i++)
//		{
//			pos0[i]--;
//		}
		update(1, 0, M - 1, was + 1, M, 1);
//		for (int i = val + 1; i < M; i++)
//		{
//			pos0[i]++;
//		}
		update(1, 0, M - 1, val + 1, M, -1);
//		pos0[val] = 0;
//		for (int i = 0; i < N; i++)
//		{
//			if (arr[i] < val)
//			{
////				pos0[val]++;
//				update(1, 0, M - 1, val, val, -1);
//			}
//		}
		update(1, 0, M - 1, val, val, -get(val - 1));
		ans[q] = query(1, 0, M - 1, 0, M - 1);
//		for (int i = 0; i < N; i++)
//		{
//			ckmax(ans[q], pos1[arr[i]] - pos0[arr[i]]);
//		}
	}
	vi res(Q);
	for (int i = 0; i < Q; i++)
	{
		res[i] = ans[i];
	}
	return res;
}

Subtask #1

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	504 KB	Output is correct
2	Correct	7 ms	632 KB	Output is correct
3	Correct	12 ms	900 KB	Output is correct
4	Correct	9 ms	1012 KB	Output is correct
5	Correct	12 ms	1192 KB	Output is correct
6	Correct	10 ms	1192 KB	Output is correct
7	Correct	9 ms	1192 KB	Output is correct
8	Correct	10 ms	1260 KB	Output is correct
9	Correct	10 ms	1260 KB	Output is correct
10	Correct	9 ms	1372 KB	Output is correct
11	Correct	9 ms	1468 KB	Output is correct
12	Correct	9 ms	1468 KB	Output is correct
13	Correct	10 ms	1480 KB	Output is correct
14	Correct	11 ms	1648 KB	Output is correct
15	Correct	11 ms	1648 KB	Output is correct
16	Correct	12 ms	1648 KB	Output is correct
17	Correct	10 ms	1648 KB	Output is correct
18	Correct	9 ms	1704 KB	Output is correct

Subtask #2

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	504 KB	Output is correct
2	Correct	7 ms	632 KB	Output is correct
3	Correct	12 ms	900 KB	Output is correct
4	Correct	9 ms	1012 KB	Output is correct
5	Correct	12 ms	1192 KB	Output is correct
6	Correct	10 ms	1192 KB	Output is correct
7	Correct	9 ms	1192 KB	Output is correct
8	Correct	10 ms	1260 KB	Output is correct
9	Correct	10 ms	1260 KB	Output is correct
10	Correct	9 ms	1372 KB	Output is correct
11	Correct	9 ms	1468 KB	Output is correct
12	Correct	9 ms	1468 KB	Output is correct
13	Correct	10 ms	1480 KB	Output is correct
14	Correct	11 ms	1648 KB	Output is correct
15	Correct	11 ms	1648 KB	Output is correct
16	Correct	12 ms	1648 KB	Output is correct
17	Correct	10 ms	1648 KB	Output is correct
18	Correct	9 ms	1704 KB	Output is correct
19	Correct	33 ms	2616 KB	Output is correct
20	Correct	35 ms	2928 KB	Output is correct
21	Correct	44 ms	3104 KB	Output is correct
22	Correct	32 ms	3348 KB	Output is correct
23	Correct	34 ms	3560 KB	Output is correct
24	Correct	39 ms	3708 KB	Output is correct
25	Correct	43 ms	3744 KB	Output is correct
26	Correct	31 ms	3904 KB	Output is correct
27	Correct	44 ms	4068 KB	Output is correct
28	Correct	49 ms	4236 KB	Output is correct

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	5040 KB	Output is correct
2	Correct	133 ms	7448 KB	Output is correct
3	Correct	349 ms	10672 KB	Output is correct
4	Correct	255 ms	11112 KB	Output is correct
5	Correct	304 ms	11808 KB	Output is correct
6	Correct	360 ms	12388 KB	Output is correct
7	Correct	386 ms	12844 KB	Output is correct
8	Correct	322 ms	13416 KB	Output is correct
9	Correct	310 ms	14004 KB	Output is correct
10	Correct	200 ms	14004 KB	Output is correct
11	Correct	274 ms	14004 KB	Output is correct
12	Correct	230 ms	14496 KB	Output is correct
13	Correct	220 ms	15072 KB	Output is correct
14	Correct	219 ms	15864 KB	Output is correct
15	Correct	195 ms	16456 KB	Output is correct
16	Correct	237 ms	17156 KB	Output is correct
17	Correct	194 ms	17756 KB	Output is correct
18	Correct	222 ms	18276 KB	Output is correct

Subtask #4

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	504 KB	Output is correct
2	Correct	7 ms	632 KB	Output is correct
3	Correct	12 ms	900 KB	Output is correct
4	Correct	9 ms	1012 KB	Output is correct
5	Correct	12 ms	1192 KB	Output is correct
6	Correct	10 ms	1192 KB	Output is correct
7	Correct	9 ms	1192 KB	Output is correct
8	Correct	10 ms	1260 KB	Output is correct
9	Correct	10 ms	1260 KB	Output is correct
10	Correct	9 ms	1372 KB	Output is correct
11	Correct	9 ms	1468 KB	Output is correct
12	Correct	9 ms	1468 KB	Output is correct
13	Correct	10 ms	1480 KB	Output is correct
14	Correct	11 ms	1648 KB	Output is correct
15	Correct	11 ms	1648 KB	Output is correct
16	Correct	12 ms	1648 KB	Output is correct
17	Correct	10 ms	1648 KB	Output is correct
18	Correct	9 ms	1704 KB	Output is correct
19	Correct	33 ms	2616 KB	Output is correct
20	Correct	35 ms	2928 KB	Output is correct
21	Correct	44 ms	3104 KB	Output is correct
22	Correct	32 ms	3348 KB	Output is correct
23	Correct	34 ms	3560 KB	Output is correct
24	Correct	39 ms	3708 KB	Output is correct
25	Correct	43 ms	3744 KB	Output is correct
26	Correct	31 ms	3904 KB	Output is correct
27	Correct	44 ms	4068 KB	Output is correct
28	Correct	49 ms	4236 KB	Output is correct
29	Correct	52 ms	5040 KB	Output is correct
30	Correct	133 ms	7448 KB	Output is correct
31	Correct	349 ms	10672 KB	Output is correct
32	Correct	255 ms	11112 KB	Output is correct
33	Correct	304 ms	11808 KB	Output is correct
34	Correct	360 ms	12388 KB	Output is correct
35	Correct	386 ms	12844 KB	Output is correct
36	Correct	322 ms	13416 KB	Output is correct
37	Correct	310 ms	14004 KB	Output is correct
38	Correct	200 ms	14004 KB	Output is correct
39	Correct	274 ms	14004 KB	Output is correct
40	Correct	230 ms	14496 KB	Output is correct
41	Correct	220 ms	15072 KB	Output is correct
42	Correct	219 ms	15864 KB	Output is correct
43	Correct	195 ms	16456 KB	Output is correct
44	Correct	237 ms	17156 KB	Output is correct
45	Correct	194 ms	17756 KB	Output is correct
46	Correct	222 ms	18276 KB	Output is correct
47	Correct	1002 ms	38368 KB	Output is correct
48	Correct	3497 ms	85188 KB	Output is correct
49	Correct	4002 ms	101628 KB	Output is correct
50	Correct	3817 ms	114556 KB	Output is correct
51	Correct	3872 ms	127352 KB	Output is correct
52	Correct	4075 ms	140144 KB	Output is correct
53	Correct	4378 ms	153232 KB	Output is correct
54	Correct	3673 ms	166236 KB	Output is correct
55	Correct	3719 ms	179420 KB	Output is correct
56	Correct	3481 ms	192180 KB	Output is correct
57	Correct	3854 ms	205260 KB	Output is correct
58	Correct	3776 ms	218060 KB	Output is correct
59	Correct	3761 ms	228168 KB	Output is correct
60	Correct	3474 ms	239348 KB	Output is correct
61	Correct	3786 ms	250972 KB	Output is correct
62	Correct	3335 ms	261156 KB	Output is correct
63	Correct	3400 ms	272420 KB	Output is correct
64	Correct	3189 ms	283128 KB	Output is correct
65	Correct	3182 ms	292972 KB	Output is correct
66	Correct	3165 ms	303092 KB	Output is correct
67	Correct	3546 ms	312060 KB	Output is correct