Submission #761494

#	Time	Username	Problem	Language	Result	Execution time	Memory
761494		raysh07	Sequence (APIO23_sequence)	C++17	100 / 100	860 ms	64516 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

struct Node{
	int prefmx, prefmn, sufmx, sufmn, tot, val, totmn, totmx;
};

const int N = 5e5 + 69;
Node seg[4 * N];
Node res;
int n;

Node combine(Node a, Node b){
	Node ok;
	ok.tot = a.tot + b.tot;
	ok.prefmx = max(a.prefmx, b.prefmx + a.totmx);
	ok.prefmn = min(a.prefmn, b.prefmn + a.totmn);
	ok.sufmx = max(b.sufmx, a.sufmx + b.totmx);
	ok.sufmn = min(b.sufmn, a.sufmn + b.totmn);
	ok.val = a.val + b.val;
	ok.totmx = a.totmx + b.totmx;
	ok.totmn = a.totmn + b.totmn;
	return ok;
}

void upd(int l, int r, int pos, int qp, int v){
	if (l == r){
		seg[pos].tot = seg[pos].totmn = seg[pos].totmx = v;
		seg[pos].prefmx = max(v, 0);
		seg[pos].prefmn = min(v, 0);
		seg[pos].sufmx = max(v, 0);
		seg[pos].sufmn = min(v, 0);
		seg[pos].val = v == 0;
		if (v == 0){
			seg[pos].sufmx = 1;
			seg[pos].sufmn = -1;
			seg[pos].prefmn = -1;
			seg[pos].prefmx = 1;
			seg[pos].totmn = -1;
			seg[pos].totmx = 1;
		}
		return;
	}

	int mid = (l + r)/2;
	if (qp <= mid) upd(l, mid, pos*2, qp, v);
	else upd(mid + 1, r, pos*2 + 1, qp, v);

	seg[pos] = combine(seg[pos * 2], seg[pos * 2 + 1]);
}

void query(int l, int r, int pos, int ql, int qr){
	if (l >= ql && r <= qr) {
		res = combine(res, seg[pos]);
		return;
	} else if (l > qr || r < ql) return;

	int mid = (l + r)/2;
	query(l, mid, pos*2, ql, qr);
	query(mid + 1, r, pos*2 + 1, ql, qr);
}

Node query(int ql, int qr){
	res.tot = res.prefmx = res.prefmn = res.sufmx = res.sufmn = res.val = res.totmn = res.totmx = 0;
	query(0, n - 1, 1, ql, qr);
	return res;
}

void print(Node a){
	cout << a.tot << " " << a.val << " " << a.sufmx << " " << a.sufmn << " " << a.prefmx << " " << a.prefmn << "\n";
}

bool good(int a, int b){
	Node g1 = query(a, b);
	Node g2 = query(0, a - 1);
	Node g3 = query(b + 1, n - 1);

	// cout << a << " " << b << "\n";
	// print(g1);
	// print(g2);
	// print(g3);

	int x = g1.val;
	//balance needs to be in range (-x, x) 
	if (g1.tot + g2.sufmx + g3.prefmx < -x) return false;
	if (g1.tot + g2.sufmn + g3.prefmn > x) return false;
	return true;
}

int sequence(int m, vector <int> a){
	//l1 < a + l2 
	//l2 < a + l1
	//l1 - l2 < a
	//l2 -l1 < a, l1 - l2 > -a
	//l1 - l2 in range (-a, a)
	//l1 is smaller stuff
	//l2 is larger stuff 
	n = m;
	vector <int> adj[n + 1];

	for (int i = 0; i < n; i++){
		upd(0, n - 1, 1, i, 1);
		adj[a[i]].push_back(i);
	}

	int ans = 0;

	for (int i = 1; i <= n; i++){
		for (auto x : adj[i]){
			upd(0, n - 1, 1, x, 0);
		}

		int r = 0;
		for (int l = 0; l < adj[i].size(); l++){
			r = max(r, l);
			while ((r + 1) < adj[i].size() && good(adj[i][l], adj[i][r + 1])){
				r++;
			}

		//	cout << "L " << l << " " << r << "\n";

			ans = max(ans, r - l + 1);
		}

		// for (int l = 0; l < (int)adj[i].size(); l++){
		// 	for (int r = l; r < (int)adj[i].size(); r++){
		// 		if (good(adj[i][l], adj[i][r])) ans = max(ans, r - l + 1);
		// 	}
		// }

		for (auto x : adj[i]){
			upd(0, n - 1, 1, x, -1);
		}
	}

	return ans;
}

// int main(){
// 	int n; cin >> n;

// 	vector <int> a(n);
// 	for (auto &x : a) cin >> x;

// 	cout << sequence(n, a) << "\n";
// 	return 0;
// }

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:114:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for (int l = 0; l < adj[i].size(); l++){
      |                   ~~^~~~~~~~~~~~~~~
sequence.cpp:116:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |    while ((r + 1) < adj[i].size() && good(adj[i][l], adj[i][r + 1])){
      |           ~~~~~~~~^~~~~~~~~~~~~~~

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