Submission #1002330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002330		0npata	Sequence (APIO23_sequence)	C++17	100 / 100	1371 ms	90220 KiB

sequence

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

#define vec vector

const int INF = 1e9;

struct SegNode {
	int mx = -INF;
	int mn = INF;

	SegNode merge(SegNode other) {
		return {max(mx, other.mx), min(mn, other.mn)};
	}
};

struct SegTree {
	vec<SegNode> data;
	vec<int> lazy;
	vec<pair<SegNode, int>> suff_cache;
	vec<pair<SegNode, int>> pref_cache;
	int n;

	int upd_ind = 1;



	SegTree(vec<int> init_data) {
		n = 1;
		while(n<init_data.size()) n*=2;

		data = vec<SegNode>(n*2);
		lazy = vec(n*2, 0);
		suff_cache = vec<pair<SegNode, int>>(n);
		pref_cache = vec<pair<SegNode, int>>(n);

		for(int i = 0; i<init_data.size(); i++) {
			data[i+n] = {init_data[i], init_data[i]};
		}

		for(int i = n-1; i > 0; i--) {
			data[i] = data[i*2].merge(data[i*2+1]);
		}
	}

	SegNode query_suffix(int l) {
		if(suff_cache[l].second != upd_ind) suff_cache[l] = {query(l, n), upd_ind};

		return suff_cache[l].first;
	}

	SegNode query_prefix(int r) {
		if(pref_cache[r-1].second != upd_ind) pref_cache[r-1] = {query(0, r), upd_ind};

		return pref_cache[r-1].first;
	}

	void push(int i) {
		data[i].mx += lazy[i];
		data[i].mn += lazy[i];
		if(i*2 > n*2) {
			lazy[i] = 0;
			return;
		}
		lazy[i*2] += lazy[i];
		lazy[i*2+1] += lazy[i];
		lazy[i] = 0;
	}

	SegNode query(int l, int r, int i = 1, int ll = 0, int rr = -1) {
		if(rr == -1) rr = n;

		push(i);

		if(ll >= r || rr <= l) return {};
		if(ll >= l && rr <= r) return data[i];

		int mm = (ll+rr)/2;
		return query(l, r, i*2, ll, mm).merge(query(l, r, i*2+1, mm, rr));
	}

	void upd(int l, int r, int val, int i = 1, int ll = 0, int rr = -1) {
		upd_ind++;

		if(rr == -1) rr = n;

		push(i);

		if(ll >= r || rr <= l) return;
		if(ll >= l && rr <= r) {
			lazy[i] += val;
			push(i);
			return;
		}

		int mm = (ll+rr)/2;
		upd(l, r, val, i*2, ll, mm);
		upd(l, r, val, i*2+1, mm, rr);

		data[i] = data[i*2].merge(data[i*2+1]);
	}
};

int sequence(int n, std::vector<int> a) {

	int ans = 0;

	vec<vec<int>> val_inds(n+1);
	for(int i = 0; i<n; i++) {
		val_inds[a[i]].push_back(i);
	}

	vec<int> st1_init(n+1);
	vec<int> st2_init(n+1);

	iota(st1_init.begin(), st1_init.end(), 0);
	iota(st2_init.begin(), st2_init.end(), 0);

	SegTree st1(st1_init);
	SegTree st2(st2_init);

	for(int i = 1; i<=n; i++) {
		for(int j = 0; j<val_inds[i-1].size(); j++) {
			st1.upd(val_inds[i-1][j]+1, n+1, -2);
		}

		for(int j = 0; j<val_inds[i].size(); j++) {
			st2.upd(val_inds[i][j]+1, n+1, -2);
		}

		int k_l = 1;
		int k_r = val_inds[i].size()+1;

		while(k_l < k_r) {
			int k = (k_l+k_r)/2;

			bool found = false;
			for(int j = k-1; j<val_inds[i].size(); j++) {
				int l = val_inds[i][j-(k-1)];
				int r = val_inds[i][j]+1;

				if(st1.query_suffix(r).mx - st1.query_prefix(l+1).mn >= 0 &&
					st2.query_suffix(r).mn - st2.query_prefix(l+1).mx <= 0) {
					ans = max(ans, k);
					found = true;
					break;
				}
			}

			if(found) k_l = k+1;
			else k_r = k;
		}
	}


	return ans;
}

Compilation message (stderr)

sequence.cpp: In constructor 'SegTree::SegTree(std::vector<int>)':
sequence.cpp:31:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   while(n<init_data.size()) n*=2;
      |         ~^~~~~~~~~~~~~~~~~
sequence.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for(int i = 0; i<init_data.size(); i++) {
      |                  ~^~~~~~~~~~~~~~~~~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:124:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |   for(int j = 0; j<val_inds[i-1].size(); j++) {
      |                  ~^~~~~~~~~~~~~~~~~~~~~
sequence.cpp:128:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |   for(int j = 0; j<val_inds[i].size(); j++) {
      |                  ~^~~~~~~~~~~~~~~~~~~
sequence.cpp:139:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |    for(int j = k-1; j<val_inds[i].size(); j++) {
      |                     ~^~~~~~~~~~~~~~~~~~~

• 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