Submission #1171996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171996		Mher777	Sequence (APIO23_sequence)	C++20	41 / 100	2096 ms	58340 KiB

sequence

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <array>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <utility>
#include <random>
#include <cassert>
#include <fstream>
#include "sequence.h"
using namespace std;
mt19937 rnd(7069);
typedef int itn;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef float fl;
typedef long double ld;
using vi = vector<int>;
using vll = vector<ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define ff first
#define ss second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mpr make_pair
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define all(x) (x).begin(), (x).end()
const int MAX = int(2e9 + 5);
const ll MAXL = ll(1e18) + 5ll;

const int max_N = 500005;
vi g[max_N];
pii pref[max_N * 4], suf[max_N * 4], lazy[max_N * 4];
int a[max_N];
int n, ans = 1;

void merge(int pos) {
	pref[pos].ff = min(pref[2 * pos].ff, pref[2 * pos + 1].ff);
	pref[pos].ss = max(pref[2 * pos].ss, pref[2 * pos + 1].ss);
	suf[pos].ff = min(suf[2 * pos].ff, suf[2 * pos + 1].ff);
	suf[pos].ss = max(suf[2 * pos].ss, suf[2 * pos + 1].ss);
}

void push(int pos) {
	pref[2 * pos].ff += lazy[pos].ff;
	pref[2 * pos].ss += lazy[pos].ff;
	pref[2 * pos + 1].ff += lazy[pos].ff;
	pref[2 * pos + 1].ss += lazy[pos].ff;
	suf[2 * pos].ff += lazy[pos].ss;
	suf[2 * pos].ss += lazy[pos].ss;
	suf[2 * pos + 1].ff += lazy[pos].ss;
	suf[2 * pos + 1].ss += lazy[pos].ss;
	lazy[2 * pos].ff += lazy[pos].ff;
	lazy[2 * pos + 1].ff += lazy[pos].ff;
	lazy[2 * pos].ss += lazy[pos].ss;
	lazy[2 * pos + 1].ss += lazy[pos].ss;
	lazy[pos] = { 0,0 };
}

void bld(int l = 1, int r = n, int pos = 1) {
	if (l == r) {
		pref[pos] = { l,l };
		suf[pos] = { n - l + 1, n - l + 1 };
		return;
	}
	int mid = (l + r) / 2;
	bld(l, mid, 2 * pos);
	bld(mid + 1, r, 2 * pos + 1);
	merge(pos);
}

void upd_pref(int l, int r, int val, int tl = 1, int tr = n, int pos = 1) {
	if (l == tl && r == tr) {
		lazy[pos].ff += val;
		pref[pos].ff += val;
		pref[pos].ss += val;
		return;
	}
	push(pos);
	int mid = (tl + tr) / 2;
	if (mid >= r) {
		upd_pref(l, r, val, tl, mid, 2 * pos);
	}
	else if (mid < l) {
		upd_pref(l, r, val, mid + 1, tr, 2 * pos + 1);
	}
	else {
		upd_pref(l, mid, val, tl, mid, 2 * pos);
		upd_pref(mid + 1, r, val, mid + 1, tr, 2 * pos + 1);
	}
	merge(pos);
}

void upd_suf(int l, int r, int val, int tl = 1, int tr = n, int pos = 1) {
	if (l == tl && r == tr) {
		lazy[pos].ss += val;
		suf[pos].ff += val;
		suf[pos].ss += val;
		return;
	}
	push(pos);
	int mid = (tl + tr) / 2;
	if (mid >= r) {
		upd_suf(l, r, val, tl, mid, 2 * pos);
	}
	else if (mid < l) {
		upd_suf(l, r, val, mid + 1, tr, 2 * pos + 1);
	}
	else {
		upd_suf(l, mid, val, tl, mid, 2 * pos);
		upd_suf(mid + 1, r, val, mid + 1, tr, 2 * pos + 1);
	}
	merge(pos);
}

pii qry(int l, int r, int type, int tl = 1, int tr = n, int pos = 1) {
	if (l <= 0 || l > r) return { 0,0 };
	if (l == tl && r == tr) {
		return (type == 1 ? pref[pos] : suf[pos]);
	}
	push(pos);
	int mid = (tl + tr) / 2;
	if (mid >= r) {
		return qry(l, r, type, tl, mid, 2 * pos);
	}
	if (mid < l) {
		return qry(l, r, type, mid + 1, tr, 2 * pos + 1);
	}
	pii opt1 = qry(l, mid, type, tl, mid, 2 * pos);
	pii opt2 = qry(mid + 1, r, type, mid + 1, tr, 2 * pos + 1);
	return { min(opt1.ff,opt2.ff),max(opt1.ss,opt2.ss) };
}

int sequence(int N, std::vector<int> A) {
	n = N;
	for (int i = 1; i <= n; ++i) {
		a[i] = A[i - 1];
		g[a[i]].pub(i);
	}
	bld();
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < (int)g[i].size(); ++j) {
			upd_pref(g[i][j], n, -1);
			upd_suf(1, g[i][j], -1);
		}
		for (int k1 = 0; k1 < (int)g[i].size(); ++k1) {
			int cnt = 1;
			for (int k2 = k1 + 1; k2 < (int)g[i].size(); ++k2) {
				++cnt;
				int l = g[i][k1], r = g[i][k2];
				int val = qry(r, r, 1).ff - qry(l - 1, l - 1, 1).ff;
				int dif;
				if (val > cnt) {
					dif = qry(1, l, 2).ff - qry(l, l, 2).ff + qry(r, n, 1).ff - qry(r, r, 1).ff;
					if (val + dif <= cnt) {
						ans = max(ans, cnt);
					}
				}
				else if (val < -cnt) {
					dif = qry(1, l, 2).ss - qry(l, l, 2).ss + qry(r, n, 1).ss - qry(r, r, 1).ss;
					if (val + dif >= -cnt) {
						ans = max(ans, cnt);
					}
				}
				else {
					ans = max(ans, cnt);
				}
			}
		}
		for (int j = 0; j < (int)g[i].size(); ++j) {
			upd_pref(g[i][j], n, -1);
			upd_suf(1, g[i][j], -1);
		}
	}
	return ans;
}

/*
9
1 1 2 3 4 3 2 1 1

14
2 6 2 5 3 4 2 1 4 3 5 6 3 2
*/

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