oj.uz

Submission #874655

# Submission time Handle Problem Language Result Execution time Memory
874655 2023-11-17T13:38:49 Z Itamar Sequence (APIO23_sequence) C++17
70 / 100
 2000 ms 97052 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) {
			sum2 = 1,maxl=1,maxr=1;
			if (p == 2) {
				sum1 = 1, minl = 0, minr = 0;
			}
		}
		else {
			if (i <= mid)sl->update(i, p);
			else sr->update(i, p);
			sum1 = sl->sum1 + sr->sum1;
			sum2 = sl->sum2 + sr->sum2;
			minl = min(sl->minl, sl->sum1 + sr->minl);
			minr = min(sr->minr, sr->sum1 + sl->minr);
			maxl = max(sl->maxl, sl->sum2 + sr->maxl);
			maxr = max(sr->maxr, sr->sum2 + sl->maxr);
		}
	}
	int query1(int a, int b) {
		if (a>r || b <l)return 0;
		 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 > r || b < l)return 0;
		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:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   while (it2+1 < his[i].size()) {
      |          ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 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 12124 KB Output is correct
6 Correct 3 ms 12156 KB Output is correct
7 Correct 4 ms 12124 KB Output is correct
8 Correct 4 ms 12124 KB Output is correct
9 Correct 4 ms 12124 KB Output is correct
10 Correct 4 ms 12124 KB Output is correct
11 Correct 3 ms 12124 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 12124 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 12124 KB Output is correct
6 Correct 3 ms 12156 KB Output is correct
7 Correct 4 ms 12124 KB Output is correct
8 Correct 4 ms 12124 KB Output is correct
9 Correct 4 ms 12124 KB Output is correct
10 Correct 4 ms 12124 KB Output is correct
11 Correct 3 ms 12124 KB Output is correct
12 Correct 3 ms 12124 KB Output is correct
13 Correct 4 ms 12380 KB Output is correct
14 Correct 4 ms 12380 KB Output is correct
15 Correct 6 ms 12428 KB Output is correct
16 Correct 6 ms 12380 KB Output is correct
17 Correct 6 ms 12424 KB Output is correct
18 Correct 4 ms 12380 KB Output is correct
19 Correct 4 ms 12380 KB Output is correct
20 Correct 4 ms 12380 KB Output is correct
21 Correct 5 ms 12380 KB Output is correct
22 Correct 5 ms 12380 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 787 ms 88624 KB Output is correct
3 Correct 690 ms 92112 KB Output is correct
4 Correct 774 ms 81624 KB Output is correct
5 Correct 775 ms 90964 KB Output is correct
6 Correct 882 ms 90904 KB Output is correct
7 Correct 861 ms 82436 KB Output is correct
8 Correct 1012 ms 82768 KB Output is correct
9 Correct 657 ms 81772 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 1459 ms 80668 KB Output is correct
3 Execution timed out 2015 ms 81656 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 94344 KB Output is correct
2 Correct 435 ms 94220 KB Output is correct
3 Correct 473 ms 93772 KB Output is correct
4 Correct 438 ms 97052 KB Output is correct
5 Correct 403 ms 93636 KB Output is correct
6 Correct 401 ms 93648 KB Output is correct
7 Correct 320 ms 92572 KB Output is correct
8 Correct 338 ms 92156 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 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 12124 KB Output is correct
6 Correct 3 ms 12156 KB Output is correct
7 Correct 4 ms 12124 KB Output is correct
8 Correct 4 ms 12124 KB Output is correct
9 Correct 4 ms 12124 KB Output is correct
10 Correct 4 ms 12124 KB Output is correct
11 Correct 3 ms 12124 KB Output is correct
12 Correct 3 ms 12124 KB Output is correct
13 Correct 4 ms 12380 KB Output is correct
14 Correct 4 ms 12380 KB Output is correct
15 Correct 6 ms 12428 KB Output is correct
16 Correct 6 ms 12380 KB Output is correct
17 Correct 6 ms 12424 KB Output is correct
18 Correct 4 ms 12380 KB Output is correct
19 Correct 4 ms 12380 KB Output is correct
20 Correct 4 ms 12380 KB Output is correct
21 Correct 5 ms 12380 KB Output is correct
22 Correct 5 ms 12380 KB Output is correct
23 Correct 93 ms 24852 KB Output is correct
24 Correct 93 ms 24852 KB Output is correct
25 Correct 99 ms 24852 KB Output is correct
26 Correct 240 ms 23892 KB Output is correct
27 Correct 250 ms 23668 KB Output is correct
28 Correct 242 ms 23888 KB Output is correct
29 Correct 294 ms 23372 KB Output is correct
30 Correct 293 ms 23132 KB Output is correct
31 Correct 53 ms 23504 KB Output is correct
32 Correct 41 ms 25624 KB Output is correct
33 Correct 92 ms 24668 KB Output is correct
34 Correct 98 ms 24676 KB Output is correct
35 Correct 88 ms 24624 KB Output is correct
36 Correct 159 ms 24656 KB Output is correct
37 Correct 120 ms 24668 KB Output is correct
38 Correct 125 ms 24684 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 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 12124 KB Output is correct
6 Correct 3 ms 12156 KB Output is correct
7 Correct 4 ms 12124 KB Output is correct
8 Correct 4 ms 12124 KB Output is correct
9 Correct 4 ms 12124 KB Output is correct
10 Correct 4 ms 12124 KB Output is correct
11 Correct 3 ms 12124 KB Output is correct
12 Correct 3 ms 12124 KB Output is correct
13 Correct 4 ms 12380 KB Output is correct
14 Correct 4 ms 12380 KB Output is correct
15 Correct 6 ms 12428 KB Output is correct
16 Correct 6 ms 12380 KB Output is correct
17 Correct 6 ms 12424 KB Output is correct
18 Correct 4 ms 12380 KB Output is correct
19 Correct 4 ms 12380 KB Output is correct
20 Correct 4 ms 12380 KB Output is correct
21 Correct 5 ms 12380 KB Output is correct
22 Correct 5 ms 12380 KB Output is correct
23 Correct 787 ms 88624 KB Output is correct
24 Correct 690 ms 92112 KB Output is correct
25 Correct 774 ms 81624 KB Output is correct
26 Correct 775 ms 90964 KB Output is correct
27 Correct 882 ms 90904 KB Output is correct
28 Correct 861 ms 82436 KB Output is correct
29 Correct 1012 ms 82768 KB Output is correct
30 Correct 657 ms 81772 KB Output is correct
31 Correct 1459 ms 80668 KB Output is correct
32 Execution timed out 2015 ms 81656 KB Time limit exceeded
33 Halted 0 ms 0 KB -