Submission #835553

#	Time	Username	Problem	Language	Result	Execution time	Memory
835553		jmyszka2007	Sequence (APIO23_sequence)	C++17	63 / 100	2052 ms	68964 KiB

sequence

#include <bits/stdc++.h>
#include <fstream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class A, class B>
ostream& operator<<(ostream& o, const pair<A, B>& p) {return o << '(' << p.first << ", " << p.second << ')';}
template<size_t Index = 0, typename... Types>
ostream& printTupleElements(ostream& o, const tuple<Types...>& t) {if constexpr (Index < sizeof...(Types)){if(Index > 0){o << ", ";}o << get<Index>(t);printTupleElements<Index + 1>(o, t);}return o;}
template<typename... Types>
ostream& operator<<(ostream& o, const tuple<Types...>& t){o << "(";printTupleElements(o, t);return o << ")";}
template<class T>
auto operator<<(ostream& o, const T& x) -> decltype(x.end(), o){o << '{';bool first = true;for (const auto& e : x){if (!first){o << ", ";}o << e;first = false;} return o << '}';}
//#define DEBUG
#ifdef DEBUG
#define fastio()
#define debug(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n'
#define check(x) if (!(x)) { cerr << "Check failed: " << #x << " in line " << __LINE__ << endl; exit(1); }
#else
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(...)
#define check(x) 
#endif
typedef long long ll;
#define pi pair<int, int>
#define pl pair<ll, ll>
#define st first
#define nd second
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
constexpr int base = (1 << 19);
int tri[2 * base][4];//tri[0] - minimum, tri[1] - maximum
int lazy[2 * base][4];//tri[0] - minimum, tri[1] - maximum
void spl(int v, int k) {
	tri[2 * v][k] += lazy[v][k];
	tri[2 * v + 1][k] += lazy[v][k];
	lazy[2 * v][k] += lazy[v][k];
	lazy[2 * v + 1][k] += lazy[v][k];
	lazy[v][k] = 0;
}
void upd(int v, int l, int r, int a, int b, int x, int k) {
	if(b < l || r < a) {
		return;
	}
	if(a <= l && r <= b) {
		tri[v][k] += x;
		lazy[v][k] += x;
		return;
	}
	spl(v, k);
	int mid = (l + r) / 2;
	upd(2 * v, l, mid, a, b, x, k);
	upd(2 * v + 1, mid + 1, r, a, b, x, k);
	if(!k || k == 3) {
		tri[v][k] = min(tri[2 * v][k], tri[2 * v + 1][k]);
	}
	else {
		tri[v][k] = max(tri[2 * v][k], tri[2 * v + 1][k]);
	}
}
int que(int v, int l, int r, int a, int b, int k) {
	if(b < l || r < a) {
		if(!k || k == 3) {
			return 1e9;
		}
		else {
			return -1e9;
		}
	}
	if(a <= l && r <= b) {
		return tri[v][k];
	}
	spl(v, k);
	int mid = (l + r) / 2;
	int ans;
	if(!k || k == 3) {
		ans = 1e9;
		ans = min(ans, que(2 * v, l, mid, a, b, k));
		ans = min(ans, que(2 * v + 1, mid + 1, r, a, b, k));
		tri[v][k] = min(tri[2 * v][k], tri[2 * v + 1][k]);
	}
	else {
		ans = -1e9;
		ans = max(ans, que(2 * v, l, mid, a, b, k));
		ans = max(ans, que(2 * v + 1, mid + 1, r, a, b, k));
		tri[v][k] = max(tri[2 * v][k], tri[2 * v + 1][k]);
	}
	return ans;
}
void init() {
	for(int i = 0; i < 2 * base; i++) {
		tri[i][0] = 1e9;
		tri[i][1] = -1e9;
		tri[i][2] = -1e9;
		tri[i][3] = 1e9;
	}
}
bool czy(int l, int r, int n) {
	int mnlft = que(1, 0, base - 1, 0, l, 0);
	int mxlft = que(1, 0, base - 1, 0, l, 2);
	int mnrgt = que(1, 0, base - 1, r, n, 3);
	int mxrgt = que(1, 0, base - 1, r, n, 1);
	if(l == 1 && r == 3) {
		debug(l, r);
		debug(mnlft, mxlft, mnrgt, mxrgt);
	}
	return ((mxrgt - mnlft) >= 0) && ((mnrgt - mxlft) <= 0);
}
int sequence(int N, std::vector<int> A) {
	//ifstream cin("nazwa.in");
	//ofstream cout("nazwa.out");
	int n;
	//cin >> n;
	n = N;
	vi tab(n + 1);
	vector<vi> wys(n + 1);
	int mx = 0;
	init();
	tri[base][0] = 0;
	tri[base][1] = 0;
	tri[base][2] = 0;
	tri[base][3] = 0;
	for(int i = 1; i <= n; i++) {
		//cin >> tab[i];
		tab[i] = A[i - 1];
		wys[tab[i]].eb(i);
		mx = max(mx, tab[i]);
		tri[i + base][0] = -i;
		tri[i + base][1] = -i;
		tri[i + base][2] = -i;
		tri[i + base][3] = -i;
	}
	for(int i = base - 1; i >= 1; i--) {
		tri[i][0] = min(tri[2 * i][0], tri[2 * i + 1][0]);
		tri[i][1] = max(tri[2 * i][1], tri[2 * i + 1][1]);
		tri[i][2] = max(tri[2 * i][2], tri[2 * i + 1][2]);
		tri[i][3] = min(tri[2 * i][3], tri[2 * i + 1][3]);
	}
	int ans = 0;
	for(int i = 1; i <= mx; i++) {
		for(auto x : wys[i]) {
			upd(1, 0, base - 1, x, n, 2, 0);
			upd(1, 0, base - 1, x, n, 2, 1);
		}
		for(int j = 0; j < sz(wys[i]); j++) {
			int l = 0;
			int r = j;
			while(l < r) {
				int mid = (l + r) / 2;
				if(czy(wys[i][mid], wys[i][j], n)) {
					r = mid;
				}
				else {
					l = mid + 1;
				}
			}
			debug(l, j);
			ans = max(ans, j - l + 1);
		}
		for(auto x : wys[i]) {
			upd(1, 0, base - 1, x, n, 2, 2);
			upd(1, 0, base - 1, x, n, 2, 3);
		}
	}
	//cout << ans << '\n';
	return ans;
}
/*int main() {
	fastio();
	int t;
	//cin >> t;
	t = 1;	
	while(t--) {
		solve();
	}
}*/

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