Submission #831603

#	Time	Username	Problem	Language	Result	Execution time	Memory
831603		pavement	Sequence (APIO23_sequence)	C++17	100 / 100	1130 ms	103516 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using dii = tuple<double, int, int>;

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define ppb pop_back

vector<int> vec[500005];
vector<iii> ev;
vector<ii> upd, qu;
set<ii> ds;
vector<set<ii>::iterator> to_erase;
int idx = 1, S[1000005], E[1000005], lft[1000005], rig[1000005], mx[1000005], mi[1000005], pv[1000005], l0[500005], l1[500005], r0[500005], r1[500005];

namespace root {

void build(int l, int r, int p = 1) {
	//~ cout << "@ " << p << ' ' << l << ' ' << r << '\n';
	S[p] = l;
	E[p] = r;
	if (l == r) {
		mx[p] = mi[p] = -l;
		return;
	}
	int M = (l + r) >> 1;
	if (l <= M) {
		lft[p] = ++idx;
		build(l, M, lft[p]);
	}
	if (M + 1 <= r) {
		rig[p] = ++idx;
		build(M + 1, r, rig[p]);
	}
	mi[p] = min(mi[lft[p]], mi[rig[p]]);
	mx[p] = max(mx[lft[p]], mx[rig[p]]);
}

void prop(int p) {
	if (S[p] == E[p] || !pv[p]) return;
	mi[lft[p]] += pv[p];
	mx[lft[p]] += pv[p];
	pv[lft[p]] += pv[p];
	mi[rig[p]] += pv[p];
	mx[rig[p]] += pv[p];
	pv[rig[p]] += pv[p];
	pv[p] = 0;
}

ii qry(int l, int r, int p = 1) {
	if (l > E[p] || r < S[p]) return mp((int)1e9, (int)-1e9);
	if (l <= S[p] && E[p] <= r) return mp(mi[p], mx[p]);
	prop(p);
	ii lq = qry(l, r, lft[p]), rq = qry(l, r, rig[p]);
	return mp(min(lq.first, rq.first), max(lq.second, rq.second));
}

void upd(int l, int r, int v, int p = 1) {
	if (l > E[p] || r < S[p]) return;
	if (l <= S[p] && E[p] <= r) {
		mi[p] += v;
		mx[p] += v;
		pv[p] += v;
		return;
	}
	prop(p);
	upd(l, r, v, lft[p]);
	upd(l, r, v, rig[p]);
	mi[p] = min(mi[lft[p]], mi[rig[p]]);
	mx[p] = max(mx[lft[p]], mx[rig[p]]);
}

};

int sequence(int N, vector<int> A) {
	int ans = 0;
	root::build(0, N - 1);
	for (int i = 0; i < N; i++) {
		vec[A[i]].pb(i);
	}	
	for (int i = 1; i <= N; i++) {
		if (vec[i].empty()) continue;
		// process v = i
		for (int j = 0; j < vec[i].size(); j++) {
			l0[j] = 1;
			r0[j] = 1;
			if (vec[i][j] > 0) {
				auto tmp = root::qry(0, vec[i][j] - 1);
				l0[j] = min(l0[j], tmp.first);
				r0[j] = max(r0[j], tmp.second);
			}
		}
		for (int j = (int)vec[i].size() - 1; j >= 0; j--) {
			l1[j] = (int)1e9;
			r1[j] = -(int)1e9;
			auto tmp = root::qry(vec[i][j], N - 1);
			l1[j] = min(l1[j], tmp.first);
			r1[j] = max(r1[j], tmp.second);
		}
		ev.clear();
		for (int j = 0; j < vec[i].size(); j++) {
			if (l0[j] <= r0[j]) {
				ev.eb(l0[j], 0, j);
				ev.eb(r0[j], 1, j);
			}
			if (l1[j] <= r1[j]) {
				ev.eb(l1[j], -2, j);
				ev.eb(r1[j], 3, j);
			}
		}
		sort(ev.begin(), ev.end());
		multiset<int> m1, m2;
		for (auto [x, t, idx] : ev) {
			if (0 <= t && t <= 1) {
				if (!m2.empty()) {
					ans = max(ans, *m2.rbegin() - idx + 1);
				}
			} else {
				if (!m1.empty()) {
					ans = max(ans, idx - *m1.begin() + 1);
				}
			}
			if (t == 0) m1.insert(idx);
			else if (t == 1) m1.erase(m1.find(idx));
			else if (t == -2) m2.insert(idx);
			else if (t == 3) m2.erase(m2.find(idx));
		}
		upd.clear();
		qu.clear();
		for (int j = 0; j < vec[i].size(); j++) {
			upd.eb(l0[j], j);
			qu.eb(r1[j], j);
		}
		ds.clear();
		to_erase.clear();
		sort(upd.begin(), upd.end(), greater<ii>());
		sort(qu.begin(), qu.end(), greater<ii>());
		for (int pt1 = 0, pt2 = 0; pt1 < upd.size() || pt2 < qu.size(); ) {
			if ((pt1 < upd.size() && pt2 < qu.size() && upd[pt1].first > qu[pt2].first) || (pt2 >= qu.size())) {
				// do upd
				int x = upd[pt1].first + 2 * upd[pt1].second, y = upd[pt1].second;
				auto it = ds.upper_bound(mp(x, (int)1e9));
				if (it != ds.begin()) {
					--it;
					if (it->second <= y) goto done;
					if (it->first < x) ++it;
				}
				while (it != ds.end() && it->second >= y) {
					to_erase.pb(it);
					++it;
				}
				for (auto it : to_erase) {
					ds.erase(it);
				}
				to_erase.clear();
				ds.emplace(x, y);
				done:;
				pt1++;
			} else {
				// do qu
				int x = qu[pt2].first + 2 * qu[pt2].second + 2;
				auto it = ds.upper_bound(mp(x, (int)1e9));
				if (it != ds.begin()) {
					--it;
					ans = max(ans, qu[pt2].second - it->second + 1);
				}
				pt2++;
			}
		}
		for (int j : vec[i]) {
			root::upd(j, N - 1, 2);
		}
	}
	return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:94:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for (int j = 0; j < vec[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~
sequence.cpp:111:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   for (int j = 0; j < vec[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~
sequence.cpp:140:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |   for (int j = 0; j < vec[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~
sequence.cpp:148:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |   for (int pt1 = 0, pt2 = 0; pt1 < upd.size() || pt2 < qu.size(); ) {
      |                              ~~~~^~~~~~~~~~~~
sequence.cpp:148:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |   for (int pt1 = 0, pt2 = 0; pt1 < upd.size() || pt2 < qu.size(); ) {
      |                                                  ~~~~^~~~~~~~~~~
sequence.cpp:149:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |    if ((pt1 < upd.size() && pt2 < qu.size() && upd[pt1].first > qu[pt2].first) || (pt2 >= qu.size())) {
      |         ~~~~^~~~~~~~~~~~
sequence.cpp:149:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |    if ((pt1 < upd.size() && pt2 < qu.size() && upd[pt1].first > qu[pt2].first) || (pt2 >= qu.size())) {
      |                             ~~~~^~~~~~~~~~~
sequence.cpp:149:88: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |    if ((pt1 < upd.size() && pt2 < qu.size() && upd[pt1].first > qu[pt2].first) || (pt2 >= qu.size())) {
      |                                                                                    ~~~~^~~~~~~~~~~~

• 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