oj.uz

Submission #874661

# Submission time Handle Problem Language Result Execution time Memory
874661 2023-11-17T13:44:51 Z Itamar Sequence (APIO23_sequence) C++17
82 / 100
 2000 ms 94496 KB 
#include "sequence.h"

#include <vector>
using namespace std;
#define vi vector<int>
const int siz = 5e5 + 1;
vi his[siz];
#define pi pair<int,int>
#define x first
#define y second
struct node {
	int l, r, mid, minl, minr, maxl, maxr,sum1,sum2;
	node* sl, * sr;
	node(int li, int ri) {
		l = li, r = ri, mid = (l + r) / 2, minl = -(r - l + 1), minr = -(r - l + 1), maxl = 0, maxr = 0,sum1=minr,sum2=minr;
		if (l < r) {
			sl = new node(l, mid);
			sr = new node(mid + 1, r);
		}
	}
	void update(int i, int p) {
		if (l == r) {
			
			if (p == 2) {
				sum1 = 1, minl = 0, minr = 0;
			}
			else {
				sum2 = 1, maxl = 1, maxr = 1;
			}
		}
		else {
			if (i <= mid)sl->update(i, p);
			else sr->update(i, p);
			if (p == 2) {
				sum1 = sl->sum1 + sr->sum1;
				minl = min(sl->minl, sl->sum1 + sr->minl);
				minr = min(sr->minr, sr->sum1 + sl->minr);
			}
			else {
				sum2 = sl->sum2 + sr->sum2;

				maxl = max(sl->maxl, sl->sum2 + sr->maxl);
				maxr = max(sr->maxr, sr->sum2 + sl->maxr);
			}
		}
	}
	int query1(int a, int b) {
		 if (a <= l && b >= r)return sum1;
		 if (b <= mid)return min(sl->query1(a, b), sl->query1(a, mid) + sr->minl);
		 if (a > mid)return min(sr->query1(a, b), sr->query1(mid + 1, b) + sl->minr);
		 return sl->query1(a, mid) + sr->query1(mid+1, b);
	}
	int query2(int a, int b) {
		if (a <= l && b >= r)return sum2;
		if (b <= mid)return max(sl->query2(a, b), sl->query2(a, mid) + sr->maxl);
		if (a > mid)return max(sr->query2(a, b), sr->query2(mid + 1, b) + sl->maxr);
		return sl->query2(a, mid) + sr->query2(mid+1, b);
	}
};

int sequence(int N, std::vector<int> A) {
	for (int i = 0; i < N; i++)his[A[i]].push_back(i);
	int ans = 1;
	node* seg = new node(0, N-1);
	for (int i = 0; i <= N; i++) {
		if (his[i].empty())continue;
		int it1 = 0, it2 = 0;
		for (int a : his[i])seg->update(a, 1);

		while (it2+1 < his[i].size()) {
			pi p = { seg->query1(his[i][it1], his[i][it2 + 1]),seg->query2(his[i][it1],his[i][it2 + 1]) };
			
			if (p.x> 0 || p.y< 0) {
				it1++;
			}
			else {
				it2++;
			}
			if (it1 > it2)it2++;
			ans = max(ans, it2 - it1 + 1);
		}

		for (int a : his[i])seg->update(a, 2);
	}

	return ans;
}

Compilation message

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:70:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   while (it2+1 < his[i].size()) {
      |          ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 3 ms 12124 KB Output is correct
5 Correct 3 ms 12120 KB Output is correct
6 Correct 3 ms 12124 KB Output is correct
7 Correct 3 ms 12124 KB Output is correct
8 Correct 3 ms 12120 KB Output is correct
9 Correct 3 ms 12120 KB Output is correct
10 Correct 3 ms 12148 KB Output is correct
11 Correct 3 ms 12120 KB Output is correct
12 Correct 3 ms 12124 KB Output is correct
13 Correct 4 ms 12376 KB Output is correct
14 Correct 4 ms 12380 KB Output is correct
15 Correct 6 ms 12380 KB Output is correct
16 Correct 6 ms 12380 KB Output is correct
17 Correct 5 ms 12380 KB Output is correct
18 Correct 3 ms 12380 KB Output is correct
19 Correct 4 ms 12380 KB Output is correct
20 Correct 4 ms 12376 KB Output is correct
21 Correct 4 ms 12380 KB Output is correct
22 Correct 4 ms 12376 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 677 ms 88656 KB Output is correct
3 Correct 560 ms 88616 KB Output is correct
4 Correct 635 ms 80600 KB Output is correct
5 Correct 661 ms 87672 KB Output is correct
6 Correct 759 ms 87676 KB Output is correct
7 Correct 720 ms 81052 KB Output is correct
8 Correct 829 ms 81184 KB Output is correct
9 Correct 532 ms 80684 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 1242 ms 80676 KB Output is correct
3 Correct 1676 ms 80672 KB Output is correct
4 Correct 1713 ms 81644 KB Output is correct
5 Correct 1176 ms 81664 KB Output is correct
6 Correct 622 ms 81648 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 94344 KB Output is correct
2 Correct 399 ms 94496 KB Output is correct
3 Correct 411 ms 93560 KB Output is correct
4 Correct 409 ms 93764 KB Output is correct
5 Correct 359 ms 90600 KB Output is correct
6 Correct 363 ms 90440 KB Output is correct
7 Correct 277 ms 89172 KB Output is correct
8 Correct 290 ms 89172 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 3 ms 12124 KB Output is correct
5 Correct 3 ms 12120 KB Output is correct
6 Correct 3 ms 12124 KB Output is correct
7 Correct 3 ms 12124 KB Output is correct
8 Correct 3 ms 12120 KB Output is correct
9 Correct 3 ms 12120 KB Output is correct
10 Correct 3 ms 12148 KB Output is correct
11 Correct 3 ms 12120 KB Output is correct
12 Correct 3 ms 12124 KB Output is correct
13 Correct 4 ms 12376 KB Output is correct
14 Correct 4 ms 12380 KB Output is correct
15 Correct 6 ms 12380 KB Output is correct
16 Correct 6 ms 12380 KB Output is correct
17 Correct 5 ms 12380 KB Output is correct
18 Correct 3 ms 12380 KB Output is correct
19 Correct 4 ms 12380 KB Output is correct
20 Correct 4 ms 12376 KB Output is correct
21 Correct 4 ms 12380 KB Output is correct
22 Correct 4 ms 12376 KB Output is correct
23 Correct 80 ms 24156 KB Output is correct
24 Correct 83 ms 24396 KB Output is correct
25 Correct 85 ms 24156 KB Output is correct
26 Correct 216 ms 23388 KB Output is correct
27 Correct 207 ms 23388 KB Output is correct
28 Correct 200 ms 23384 KB Output is correct
29 Correct 233 ms 23132 KB Output is correct
30 Correct 241 ms 23136 KB Output is correct
31 Correct 47 ms 22992 KB Output is correct
32 Correct 33 ms 25180 KB Output is correct
33 Correct 79 ms 24208 KB Output is correct
34 Correct 92 ms 24220 KB Output is correct
35 Correct 79 ms 24156 KB Output is correct
36 Correct 114 ms 24160 KB Output is correct
37 Correct 129 ms 24336 KB Output is correct
38 Correct 122 ms 24152 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Correct 3 ms 12124 KB Output is correct
5 Correct 3 ms 12120 KB Output is correct
6 Correct 3 ms 12124 KB Output is correct
7 Correct 3 ms 12124 KB Output is correct
8 Correct 3 ms 12120 KB Output is correct
9 Correct 3 ms 12120 KB Output is correct
10 Correct 3 ms 12148 KB Output is correct
11 Correct 3 ms 12120 KB Output is correct
12 Correct 3 ms 12124 KB Output is correct
13 Correct 4 ms 12376 KB Output is correct
14 Correct 4 ms 12380 KB Output is correct
15 Correct 6 ms 12380 KB Output is correct
16 Correct 6 ms 12380 KB Output is correct
17 Correct 5 ms 12380 KB Output is correct
18 Correct 3 ms 12380 KB Output is correct
19 Correct 4 ms 12380 KB Output is correct
20 Correct 4 ms 12376 KB Output is correct
21 Correct 4 ms 12380 KB Output is correct
22 Correct 4 ms 12376 KB Output is correct
23 Correct 677 ms 88656 KB Output is correct
24 Correct 560 ms 88616 KB Output is correct
25 Correct 635 ms 80600 KB Output is correct
26 Correct 661 ms 87672 KB Output is correct
27 Correct 759 ms 87676 KB Output is correct
28 Correct 720 ms 81052 KB Output is correct
29 Correct 829 ms 81184 KB Output is correct
30 Correct 532 ms 80684 KB Output is correct
31 Correct 1242 ms 80676 KB Output is correct
32 Correct 1676 ms 80672 KB Output is correct
33 Correct 1713 ms 81644 KB Output is correct
34 Correct 1176 ms 81664 KB Output is correct
35 Correct 622 ms 81648 KB Output is correct
36 Correct 391 ms 94344 KB Output is correct
37 Correct 399 ms 94496 KB Output is correct
38 Correct 411 ms 93560 KB Output is correct
39 Correct 409 ms 93764 KB Output is correct
40 Correct 359 ms 90600 KB Output is correct
41 Correct 363 ms 90440 KB Output is correct
42 Correct 277 ms 89172 KB Output is correct
43 Correct 290 ms 89172 KB Output is correct
44 Correct 80 ms 24156 KB Output is correct
45 Correct 83 ms 24396 KB Output is correct
46 Correct 85 ms 24156 KB Output is correct
47 Correct 216 ms 23388 KB Output is correct
48 Correct 207 ms 23388 KB Output is correct
49 Correct 200 ms 23384 KB Output is correct
50 Correct 233 ms 23132 KB Output is correct
51 Correct 241 ms 23136 KB Output is correct
52 Correct 47 ms 22992 KB Output is correct
53 Correct 33 ms 25180 KB Output is correct
54 Correct 79 ms 24208 KB Output is correct
55 Correct 92 ms 24220 KB Output is correct
56 Correct 79 ms 24156 KB Output is correct
57 Correct 114 ms 24160 KB Output is correct
58 Correct 129 ms 24336 KB Output is correct
59 Correct 122 ms 24152 KB Output is correct
60 Correct 782 ms 91924 KB Output is correct
61 Correct 804 ms 91928 KB Output is correct
62 Correct 792 ms 91936 KB Output is correct
63 Correct 1791 ms 83444 KB Output is correct
64 Correct 1800 ms 83280 KB Output is correct
65 Correct 1814 ms 83536 KB Output is correct
66 Correct 1948 ms 81644 KB Output is correct
67 Execution timed out 2009 ms 81656 KB Time limit exceeded
68 Halted 0 ms 0 KB -