Submission #1081532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081532		Halym2007	Sequence (APIO23_sequence)	C++17	0 / 100	2062 ms	66392 KiB

sequence

#include <bits/stdc++.h>
//#include "sequence.h"
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
const int N = 5e5 + 5;
const int NN = N * 4;
int a[N], n;
vector <int> idx[N];
ll mx[NN], mn[NN], st[NN], gosh[NN], jogg;

void build (int ind, int l, int r) {
	if (l == r) {
		st[ind] = mn[ind] = mx[ind] = l;
		return;
	}
	int mid = (l + r) / 2;
	build (ind * 2, l, mid);
	build (ind * 2 + 1, mid + 1, r);
	mn[ind] = min (mn[ind * 2], mn[ind * 2 + 1]);
	mx[ind] = max (mx[ind * 2], mx[ind * 2 + 1]);
}

void update (int ind, int l, int r, int x, int y, ll val) {
	if (gosh[ind / 2]) {
		gosh[ind] += gosh[ind / 2];
		st[ind] += (r - l + 1) * gosh[ind / 2];
		mn[ind] += gosh[ind / 2];
		mx[ind] += gosh[ind / 2];
	}
	if (x > r or l > y) {
		return;
	}
	if (x <= l and r <= y) {
		gosh[ind] += val;
		st[ind] += (r - l + 1) * val;
		mn[ind] += val;
		mx[ind] += val;
		return;
	}
	
	int mid = (l + r) / 2;
	update (ind * 2, l, mid, x, y, val);
	update (ind * 2 + 1, mid + 1, r, x, y, val);
	gosh[ind] = 0;
	st[ind] = st[ind * 2] + st[ind * 2 + 1];
	mn[ind] = min (mn[ind * 2], mn[ind * 2 + 1]);
	mx[ind] = max (mx[ind * 2], mx[ind * 2 + 1]);	
}


void uly (int ind, int l, int r, int x, int y) {
	if (gosh[ind / 2]) {
		gosh[ind] += gosh[ind / 2];
		st[ind] += (r - l + 1) * gosh[ind / 2];
		mn[ind] += gosh[ind / 2];
		mx[ind] += gosh[ind / 2];
	}
	if (x > r or l > y) {
		return;
	}
	if (x <= l and r <= y) {
		jogg = max (jogg, mx[ind]);
		return;
	}
	
	int mid = (l + r) / 2;
	uly (ind * 2, l, mid, x, y);
	uly (ind * 2 + 1, mid + 1, r, x, y);
	gosh[ind] = 0;
	st[ind] = st[ind * 2] + st[ind * 2 + 1];
	mn[ind] = min (mn[ind * 2], mn[ind * 2 + 1]);
	mx[ind] = max (mx[ind * 2], mx[ind * 2 + 1]);
}

void kici (int ind, int l, int r, int x, int y) {
	if (gosh[ind / 2]) {
		gosh[ind] += gosh[ind / 2];
		st[ind] += (r - l + 1) * gosh[ind / 2];
		mn[ind] += gosh[ind / 2];
		mx[ind] += gosh[ind / 2];
	}
	if (x > r or l > y) {
		return;
	}
	if (x <= l and r <= y) {
		jogg = min (jogg, mn[ind]);
		return;
	}
	
	int mid = (l + r) / 2;
	kici (ind * 2, l, mid, x, y);
	kici (ind * 2 + 1, mid + 1, r, x, y);
	gosh[ind] = 0;
	st[ind] = st[ind * 2] + st[ind * 2 + 1];
	mn[ind] = min (mn[ind * 2], mn[ind * 2 + 1]);
	mx[ind] = max (mx[ind * 2], mx[ind * 2 + 1]);
}


int sequence(int N, vector<int> A) {
	n = N;
	for (int i = 0; i < n; ++i) {
		a[i] = A[i];
		idx[a[i]].pb (i + 1);
	}	
//	for (int pos : idx[1]) {
//		cout << pos << " ";
//	}
//	exit(0);
	int l = 2, r = n, jog = 1;
	while (l <= r) {
		int md = (l + r) / 2;
//		md = 3;
//		cout << md << "\n";
		bool bolya = 0;
		build (1, 1, n);
		for (int i = 1; i <= n; ++i) {
			gosh[i] = 0;
		}
		jogg = -1e18;
		for (int i = 1; i <= n; ++i) {
			for (int pos : idx[i]) {//suwagt value-sy 1 bolup dur 0 owurmeli
				update (1, 1, n, pos, n, -1);
				uly (1, 1, n, 9, 10);
//				cout << jogg << "\n";
//				exit(0);
			}
			for (int pos : idx[i - 1]) {// suwagt value-sy 0 bolup dur -1 owurmeli
				update (1, 1, n, pos, n, -1);
			}
			for (int j = 0; j + md - 1 < (int)idx[i].sz; ++j) {
				ll a1, a2, b1, b2;
//				
				jogg = -1e18;
				uly (1, 1, n, idx[i][j + md - 1], n);
				a2 = jogg;
				jogg = 1e18;
				kici(1, 1, n, idx[i][j + md - 1], n);
				a1 = jogg;
				jogg = -1e18;
				uly (1, 1, n, 1, idx[i][j]); 
				b2 = jogg;
				jogg = 1e18;
				kici (1, 1, n, 1, idx[i][j]);
				b1 = jogg;
				if (b1 > 0) b1 = 0;
				if (b2 < 0) b2 = 0;
				
//					cout << "men\n";
//					cout << a1 << " " << b1 << " " << a2 << "\n";
//					cout << b1 << " " << a1 << " " << b2 << "\n";
//					cout << "men " << idx[i][j] << " " << idx[i][j + md - 1] << " " << i;
//					exit(0);
				
				if ((a1 <= b1 and b1 <= a2) or  (b1 <= a1 and a1 <= b2)) {
					bolya = 1;
					break;
				}
				int jj = max (a1, b1), jj1 = min(a2, b2);
				if ((jj <= md + jj1)) {
					bolya = 1;
//					cout << "menj\n";
//					cout << a1 << " " << b1 << " " << a2 << "\n";
//					cout << b1 << " " << a1 << " " << b2 << "\n";
//					cout << "menj " << idx[i][j] << " " << idx[i][j + md - 1] << " " << i;
//					exit(0);
					break;
				}
			}
			if (bolya) break;
		}
//		cout << bolya << "\n";
//		cout << "gutar\n";
//		exit(0);
		if (bolya) {
			l = md + 1;
			jog = md;
		}
		else {
			r = md - 1;
		}
	}
	return jog;
}
// a[i]>=1 and a[i] <= n

//int main() {
//	freopen ("input.txt", "r", stdin);
//  int N;
//  assert(1 == scanf("%d", &N));
//
//  std::vector<int> A(N);
//  for (int i = 0; i < N; ++i) {
//    assert(1 == scanf("%d", &A[i]));
//	  }
//	  int result = sequence(N, A);
//  printf("%d\n", result);
//  return 0;
//}
/*
9
1 1 2 3 4 3 2 1 1
answer : 2

7
1 2 3 1 2 1 3
answer : 3

14
2 6 2 5 3 4 2 1 4 3 5 6 3 2
answer : 3

10
1 3 1 10 5 6 1 4 1 8 
answer : 2

9
9 6 6 4 3 4 3 6 5
answer : 3
*/

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18