Submission #758493

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
758493	2023-06-14T16:39:03 Z	rainboy	Sequence (APIO23_sequence)	C++17	50 / 100	2000 ms	32708 KB

sequence

#include "sequence.h"
#include <vector>

using namespace std;

typedef vector<int> vi;

const int N = 500000, N_ = 1 << 19;	/* N_ = pow2(ceil(log2(N + 1))) */

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int aa[N], ii[N], n;
int ss1[N_ * 2], pp1[N_ * 2], qq1[N_ * 2], ss2[N_ * 2], pp2[N_ * 2], qq2[N_ * 2], n_;

void pul(int *ss, int *pp, int *qq, int i) {
	int l = i << 1, r = l | 1;
	ss[i] = ss[l] + ss[r];
	pp[i] = min(pp[l], ss[l] + pp[r]);
	qq[i] = min(qq[l] + ss[r], qq[r]);
}

void build(int *ss, int *pp, int *qq, int x) {
	for (int i = 0; i < n_; i++)
		ss[n_ + i] = i < n ? x : 0, pp[n_ + i] = qq[n_ + i] = min(ss[n_ + i], 0);
	for (int i = n_ - 1; i > 0; i--)
		pul(ss, pp, qq, i);
}

void update(int *ss, int *pp, int *qq, int i, int x) {
	i += n_;
	ss[i] = x, pp[i] = qq[i] = min(x, 0);
	while (i > 1)
		pul(ss, pp, qq, i >>= 1);
}

int query_s(int *ss, int l, int r) {
	int s = 0;
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			s += ss[l++];
		if ((r & 1) == 0)
			s += ss[r--];
	}
	return s;
}

int query_q(int *ss, int *qq, int r) {
	int l = 0, s = 0, q = 0;
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((r & 1) == 0)
			q = min(qq[r] + s, q), s += ss[r], r--;
	return q;
}

int query_p(int *ss, int *pp, int l) {
	int r = n_ - 1, s = 0, p = 0;
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((l & 1) == 1)
			p = min(p, s + pp[l]), s += ss[l], l++;
	return p;
}

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
		while (j < k) {
			int c = aa[ii[j]] != aa[i_] ? aa[ii[j]] - aa[i_] : ii[j] - i_;

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

bool solve(int k) {
	build(ss1, pp1, qq1, 1), build(ss2, pp2, qq2, -1);
	for (int i = 0, j; i < n; i = j) {
		j = i + 1;
		while (j < n && aa[ii[j]] == aa[ii[i]])
			j++;
		for (int h = i; h < j; h++) {
			int i_ = ii[h];
			update(ss1, pp1, qq1, i_, -1);
		}
		for (int h = i; h + k <= j; h++) {
			int l = ii[h], r = ii[h + k - 1], s;
			if ((s = query_s(ss1, l, r)) > 0) {
				if (query_q(ss1, qq1, l - 1) + s + query_p(ss1, pp1, r + 1) <= 0)
					return true;
			} else if ((s = query_s(ss2, l, r)) > 0) {
				if (query_q(ss2, qq2, l - 1) + s + query_p(ss2, pp2, r + 1) <= 0)
					return true;
			} else
				return true;
		}
		for (int h = i; h < j; h++) {
			int i_ = ii[h];
			update(ss2, pp2, qq2, i_, 1);
		}
	}
	return false;
}

int sequence(int n1, vi aa_) {
	n = n1;
	n_ = 1;
	while (n_ <= n)
		n_ <<= 1;
	for (int i = 0; i < n; i++) {
		aa[i] = aa_[i];
		ii[i] = i;
	}
	sort(ii, 0, n);
	int lower = 0, upper = n + 1;
	while (upper - lower > 1) {
		int k = (lower + upper) / 2;
		if (solve(k))
			lower = k;
		else
			upper = k;
	}
  return lower;
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	11 ms	476 KB	Output is correct
14	Correct	6 ms	468 KB	Output is correct
15	Correct	5 ms	468 KB	Output is correct
16	Correct	6 ms	476 KB	Output is correct
17	Correct	5 ms	468 KB	Output is correct
18	Correct	5 ms	468 KB	Output is correct
19	Correct	5 ms	468 KB	Output is correct
20	Correct	5 ms	468 KB	Output is correct
21	Correct	6 ms	468 KB	Output is correct
22	Correct	5 ms	468 KB	Output is correct

Subtask #3

0.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Execution timed out	2087 ms	32696 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4

0.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Execution timed out	2059 ms	32648 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2071 ms	32708 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	11 ms	476 KB	Output is correct
14	Correct	6 ms	468 KB	Output is correct
15	Correct	5 ms	468 KB	Output is correct
16	Correct	6 ms	476 KB	Output is correct
17	Correct	5 ms	468 KB	Output is correct
18	Correct	5 ms	468 KB	Output is correct
19	Correct	5 ms	468 KB	Output is correct
20	Correct	5 ms	468 KB	Output is correct
21	Correct	6 ms	468 KB	Output is correct
22	Correct	5 ms	468 KB	Output is correct
23	Correct	718 ms	7768 KB	Output is correct
24	Correct	538 ms	7728 KB	Output is correct
25	Correct	641 ms	7868 KB	Output is correct
26	Correct	501 ms	7776 KB	Output is correct
27	Correct	517 ms	7768 KB	Output is correct
28	Correct	450 ms	7776 KB	Output is correct
29	Correct	361 ms	7884 KB	Output is correct
30	Correct	390 ms	7768 KB	Output is correct
31	Correct	267 ms	7772 KB	Output is correct
32	Correct	379 ms	7768 KB	Output is correct
33	Correct	375 ms	7756 KB	Output is correct
34	Correct	521 ms	7772 KB	Output is correct
35	Correct	427 ms	7768 KB	Output is correct
36	Correct	467 ms	7768 KB	Output is correct
37	Correct	518 ms	7764 KB	Output is correct
38	Correct	621 ms	7724 KB	Output is correct

Subtask #7

0.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	11 ms	476 KB	Output is correct
14	Correct	6 ms	468 KB	Output is correct
15	Correct	5 ms	468 KB	Output is correct
16	Correct	6 ms	476 KB	Output is correct
17	Correct	5 ms	468 KB	Output is correct
18	Correct	5 ms	468 KB	Output is correct
19	Correct	5 ms	468 KB	Output is correct
20	Correct	5 ms	468 KB	Output is correct
21	Correct	6 ms	468 KB	Output is correct
22	Correct	5 ms	468 KB	Output is correct
23	Execution timed out	2087 ms	32696 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-