oj.uz

Submission #874657

# Submission time Handle Problem Language Result Execution time Memory
874657 2023-11-17T13:43:10 Z Itamar Sequence (APIO23_sequence) C++17
0 / 100
 1122 ms 94344 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 == 1) {
				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
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Incorrect 2 ms 12124 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Incorrect 2 ms 12124 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Correct 694 ms 88628 KB Output is correct
3 Correct 559 ms 88612 KB Output is correct
4 Correct 1122 ms 80664 KB Output is correct
5 Correct 692 ms 87672 KB Output is correct
6 Correct 769 ms 87672 KB Output is correct
7 Incorrect 762 ms 81056 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 94344 KB Output is correct
2 Correct 409 ms 94292 KB Output is correct
3 Correct 480 ms 93636 KB Output is correct
4 Correct 432 ms 93892 KB Output is correct
5 Incorrect 388 ms 90196 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Incorrect 2 ms 12124 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12120 KB Output is correct
2 Incorrect 2 ms 12124 KB Output isn't correct
3 Halted 0 ms 0 KB -