Submission #754976

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
754976	2023-06-09T07:54:07 Z	Zanite	Sequence (APIO23_sequence)	C++17	82 / 100	2000 ms	131448 KB

sequence

#include "sequence.h"

// 赤コーダーになりたい
// お願い いいですか？

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// Pragmas
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// Namespaces
using namespace std;
using namespace __gnu_pbds;

// Data types
using si	= short int;
using ll	= long long;
using lll	= __int128;
using ld	= long double;

// Pairs
using pii	= pair<int, int>;
using psi	= pair<si, si>;
using pll	= pair<ll, ll>;
using plll	= pair<lll, lll>;
using pld	= pair<ld, ld>;
#define fi	first
#define se	second

// For
#define Frue(i, n, N)		for (int i = (n); i <= (N); i++)
#define  Fru(i, n, N)		for (int i = (n); i <  (N); i++)
#define Frde(i, n, N)		for (int i = (n); i >= (N); i--)
#define  Frd(i, n, N)		for (int i = (n); i >  (N); i--)

// PBDS
template<typename Z>
using ordered_set	= tree<Z, null_type, less<Z>, rb_tree_tag, tree_order_statistics_node_update>;

// Various outputs
template<typename Y, typename Z> ostream& operator<<(ostream &os, const pair<Y, Z> &p) {
  return os << '(' << p.fi << ',' << p.se << ')';
}
template<typename Z> ostream& operator<<(ostream &os, const vector<Z> &v) {
  os << '{'; bool _first = 1;
  for (auto &i : v) {if (!_first) os << ", "; os << i; _first = 0;}
  return os << '}';
}
template<typename Z, unsigned long long sz> ostream& operator<<(ostream &os, const array<Z, sz> &arr) {
  os << '{'; bool _first = 1;
  for (auto &i : arr) {if (!_first) os << ", "; os << i; _first = 0;}
  return os << '}';
}

// Quick macro functions
#define sqr(x)			((x)*(x))
#define debug(x)		cout << #x << " = " << (x) << '\n'
#define debugV(v, x)	cout << #v << "[" << (x) << "] = " << (v[x]) << '\n'
#define rrebug(x)		cerr << #x << " = " << (x) << '\n'
#define rrebugV(v, x)	cerr << #v << "[" << (x) << "] = " << (v[x]) << '\n'

#define All(x)			x.begin(), x.end()
#define Sort(x)			sort(All(x))
#define Reverse(x)		reverse(All(x))
#define Uniqueify(x)	Sort(x); x.erase(unique(All(x)), x.end())

#define RandomSeed			chrono::steady_clock::now().time_since_epoch().count()
#define MultipleTestcases	int _tc; cin >> _tc; for (int _cur_tc = 1; _cur_tc <= _tc; _cur_tc++)

// Check min and max
template<typename Z> void chmin(Z &a, Z b) {a = min(a, b);}
template<typename Z> void chmax(Z &a, Z b) {a = max(a, b);}
 
// Modular arithmetic
template<int MOD>
class ModInt {
  public:
  int v;
  ModInt() : v(0) {}
  ModInt(long long _v) {
    v = int((-MOD < _v && _v < MOD) ? (_v) : (_v % MOD));
    if (v < 0) v += MOD;
  }
 
  friend bool operator==(const ModInt &a, const ModInt &b) {return a.v == b.v;}
  friend bool operator!=(const ModInt &a, const ModInt &b) {return a.v != b.v;}
  friend bool operator< (const ModInt &a, const ModInt &b) {return a.v <  b.v;}
  friend bool operator<=(const ModInt &a, const ModInt &b) {return a.v <= b.v;}
  friend bool operator> (const ModInt &a, const ModInt &b) {return a.v >  b.v;}
  friend bool operator>=(const ModInt &a, const ModInt &b) {return a.v >= b.v;}
 
  ModInt &operator+=(const ModInt &a) {if ((v += a.v) >= MOD) v -= MOD; return *this;}
  ModInt &operator-=(const ModInt &a) {if ((v -= a.v) < 0) v += MOD; return *this;}
  ModInt &operator*=(const ModInt &a) {v = 1ll * v * a.v % MOD; return *this;}
  ModInt &operator/=(const ModInt &a) {return (*this) *= inverse(a);}
 
  friend ModInt pow(ModInt a, long long x) {
    ModInt res = 1;
    for (; x; x /= 2, a *= a) if (x & 1) res *= a;
    return res;
  }
  friend ModInt inverse(ModInt a) {return pow(a, MOD - 2);}
 
  ModInt operator+ () const {return ModInt( v);}
  ModInt operator- () const {return ModInt(-v);}
  ModInt operator++() const {return *this += 1;}
  ModInt operator--() const {return *this -= 1;}
 
  friend ModInt operator+(ModInt a, const ModInt &b) {return a += b;}
  friend ModInt operator-(ModInt a, const ModInt &b) {return a -= b;}
  friend ModInt operator*(ModInt a, const ModInt &b) {return a *= b;}
  friend ModInt operator/(ModInt a, const ModInt &b) {return a /= b;}
 
  friend istream &operator>>(istream &is, ModInt &v) {return is >> v.v;}
  friend ostream &operator<<(ostream &os, const ModInt &v) {return os << v.v;}
};
const int ModA	= 998244353;
const int ModC	= 1e9 + 7;
using MintA	= ModInt<ModA>;
using MintC	= ModInt<ModC>;

// Other constants
const ll INF	= 1e18;
const ll iINF	= 1e9;
const ld EPS	= 1e-9;
const ld iEPS	= 1e-6;

struct SegtreeLazy {
	using Elm	= pii; // {max, min}
	using H_Elm	= int;
	Elm DEFAULT = {-iINF, iINF};

	#define m	((l+r) >> 1)
	#define lc	(pos << 1)
	#define rc	(lc | 1)

	int sz;
	vector<Elm> seg;
	vector<H_Elm> lazy;

	SegtreeLazy(int sz = 1) : sz(sz) {
		seg = vector<Elm>((sz << 2) + 1, DEFAULT);
		lazy = vector<H_Elm>((sz << 2) + 1, 0);
	}

	void updateNode(int pos, int l, int r, H_Elm val) {
		seg[pos] = {seg[pos].fi + val, seg[pos].se + val};
		lazy[pos] += val;
	}

	Elm merge(Elm a, Elm b) {
		return {max(a.fi, b.fi), min(a.se, b.se)};
	}

	void checkLazy(int pos, int l, int r) {
		if (lazy[pos]) {
			updateNode(lc, l, m, lazy[pos]);
			updateNode(rc, m+1, r, lazy[pos]);
			lazy[pos] = 0;
		}
	}

	void build(int pos, int l, int r, vector<H_Elm> &v) {
		if (l == r) {
			seg[pos] = {v[l], v[l]};
			return;
		}

		build(lc, l, m, v);
		build(rc, m+1, r, v);
		seg[pos] = merge(seg[lc], seg[rc]);
	}
	void build(vector<H_Elm> &v) {build(1, 0, sz-1, v);}

	void update(int pos, int l, int r, int ul, int ur, H_Elm val) {
		if (l > r || ul > ur || ul > r || l > ur) {return;}
		if (ul <= l && r <= ur) {
			updateNode(pos, l, r, val);
			return;
		}

		checkLazy(pos, l, r);
		update(lc, l, m, ul, ur, val);
		update(rc, m+1, r, ul, ur, val);
		seg[pos] = merge(seg[lc], seg[rc]);
	}
	void update(int ul, int ur, H_Elm val) {update(1, 0, sz-1, ul, ur, val);}

	Elm query(int pos, int l, int r, int ql, int qr) {
		if (l > r || ql > qr || ql > r || l > qr) {return DEFAULT;}
		if (ql <= l && r <= qr) {return seg[pos];}

		checkLazy(pos, l, r);
		return merge(query(lc, l, m, ql, qr), query(rc, m+1, r, ql, qr));
	}
	Elm query(int ql, int qr) {return query(1, 0, sz-1, ql, qr);}

	#undef	m
	#undef	lc
	#undef	rc
};

ostream& operator<<(ostream &os, SegtreeLazy &S) {
  for (int i = 0; i < S.sz; i++) os << S.query(i, i) << ' ';
  return os;
}

struct FenwickTree {
	using Elm	= int;

	int sz;
	vector<Elm> BIT;

	FenwickTree(int sz = 1) : sz(sz) {
		BIT.assign(sz+1, 0);
	}

	void update(int idx, Elm val) {
		idx++;
		for (; idx <= sz; idx += (idx & -idx)) {BIT[idx] += val;}
	}

	Elm sum(int idx) {
		idx++;
		Elm ret = 0;
		for (; idx > 0; idx -= (idx & -idx)) {ret += BIT[idx];}
		return ret;
 	}

	Elm query(int l, int r) {return sum(r) - sum(l-1);}
};

SegtreeLazy G_Pref, G_Suff, L_Pref, L_Suff;
FenwickTree Gr, Le;

bool check(int l, int r, int N, vector<int> &A, int val) {
    int gr = Gr.query(l, r), le = Le.query(l, r);
	int len = r - l + 1;
	int eq = len - gr - le;

    bool needGreater = (gr < le);
    int target = abs(gr - le) - eq;

	// cout << l << ' ' << r << '\n';
	// cout << gr << ' ' << le << ' ' << eq << '\n';
    // debug(needGreater);
    // debug(target);
	// cout << "---\n";
    
    int cur = 0;

	if (needGreater) {
		int cl = 0, cr = 0;
		if (l > 0) cl = G_Suff.query(0, l).fi - G_Suff.query(l, l).fi;
		if (r < N-1) cr = G_Pref.query(r, N-1).fi - G_Pref.query(r, r).fi;

		// debug(G_Suff); debug(G_Pref);
		// debug(cl); debug(cr);

		cur = max(cur, cl + cr);

		// cl = 0, cr = 0;
		// if (l > 0) cl = L_Suff.query(0, l).fi - L_Suff.query(l, l).fi;
		// if (r < N-1) cr = L_Pref.query(r, N-1).fi - L_Pref.query(r, r).fi;

		// cur = max(cur, cl + cr);
		
	} else {
		// int cl = 0, cr = 0;
		// if (l > 0) cl = G_Suff.query(0, l).se - G_Suff.query(l, l).se;
		// if (r < N-1) cr = G_Pref.query(r, N-1).se - G_Pref.query(r, r).se;

		// // debug(G_Suff); debug(G_Pref);
		// // debug(cl); debug(cr);

		// cur = max(cur, - cl - cr);

		int cl = 0, cr = 0;
		if (l > 0) cl = L_Suff.query(0, l).se - L_Suff.query(l, l).se;
		if (r < N-1) cr = L_Pref.query(r, N-1).se - L_Pref.query(r, r).se;

		// debug(L_Suff); debug(L_Pref);
		// debug(cl); debug(cr);

		cur = max(cur, - cl - cr);
	}

	// cout << '\n';

    return (cur >= target);
}

int sequence(int N, std::vector<int> A) {
    vector<vector<int>> occ(N+1);
    for (int i = 0; i < N; i++) occ[A[i]].push_back(i);

	// Greater = +1
	// Less = -1
    G_Pref = G_Suff = L_Pref = L_Suff = SegtreeLazy(N);
	Gr = Le = FenwickTree(N);

	// Initially, everything is greater
	vector<int> init(N);
	for (int i = 0; i < N; i++) init[i] = i + 1;
	G_Pref.build(init); L_Pref.build(init);

	Reverse(init);
	G_Suff.build(init); L_Suff.build(init);

	for (int i = 0; i < N; i++) Gr.update(i, 1);

    int ans = 1;
    for (int i = 1; i <= N; i++) {
        if (occ[i].empty()) continue;

		// Turn i to less in LSkew
		for (auto j : occ[i]) L_Pref.update(j, N-1, -2);
		for (auto j : occ[i]) L_Suff.update(0, j, -2);

		for (auto j : occ[i]) Gr.update(j, -1);

        int cs = (int)occ[i].size();
        for (int pl = 0, pr = -1; pl < cs; pl++) {
            while (pr + 1 < cs) {
                if (check(occ[i][pl], occ[i][pr+1], N, A, i)) pr++;
                else break;
            }

            ans = max(ans, pr - pl + 1);
        }

		// Turn i to less in GSkew
		for (auto j : occ[i]) G_Pref.update(j, N-1, -2);
		for (auto j : occ[i]) G_Suff.update(0, j, -2);

		for (auto j : occ[i]) Le.update(j, 1);
    }

    return ans;
}

#ifdef Zanite
int main() {
  int N;
  assert(1 == scanf("%d", &N));

  std::vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &A[i]));
  }

  int result = sequence(N, A);
  printf("%d\n", result);
  return 0;
}
#endif

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	4 ms	724 KB	Output is correct
14	Correct	4 ms	724 KB	Output is correct
15	Correct	4 ms	724 KB	Output is correct
16	Correct	4 ms	724 KB	Output is correct
17	Correct	4 ms	724 KB	Output is correct
18	Correct	3 ms	808 KB	Output is correct
19	Correct	4 ms	724 KB	Output is correct
20	Correct	4 ms	724 KB	Output is correct
21	Correct	6 ms	852 KB	Output is correct
22	Correct	5 ms	724 KB	Output is correct

Subtask #3

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	953 ms	125724 KB	Output is correct
3	Correct	1047 ms	125708 KB	Output is correct
4	Correct	850 ms	117780 KB	Output is correct
5	Correct	992 ms	124780 KB	Output is correct
6	Correct	985 ms	124772 KB	Output is correct
7	Correct	767 ms	118296 KB	Output is correct
8	Correct	937 ms	118432 KB	Output is correct
9	Correct	798 ms	117896 KB	Output is correct

Subtask #4

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	989 ms	118020 KB	Output is correct
3	Correct	1072 ms	117892 KB	Output is correct
4	Correct	1184 ms	117952 KB	Output is correct
5	Correct	909 ms	118108 KB	Output is correct
6	Correct	933 ms	117968 KB	Output is correct

Subtask #5

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1520 ms	131448 KB	Output is correct
2	Correct	1422 ms	131444 KB	Output is correct
3	Correct	1483 ms	130896 KB	Output is correct
4	Correct	1537 ms	130868 KB	Output is correct
5	Correct	1302 ms	127532 KB	Output is correct
6	Correct	1332 ms	127532 KB	Output is correct
7	Correct	1100 ms	126332 KB	Output is correct
8	Correct	1078 ms	126024 KB	Output is correct

Subtask #6

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	4 ms	724 KB	Output is correct
14	Correct	4 ms	724 KB	Output is correct
15	Correct	4 ms	724 KB	Output is correct
16	Correct	4 ms	724 KB	Output is correct
17	Correct	4 ms	724 KB	Output is correct
18	Correct	3 ms	808 KB	Output is correct
19	Correct	4 ms	724 KB	Output is correct
20	Correct	4 ms	724 KB	Output is correct
21	Correct	6 ms	852 KB	Output is correct
22	Correct	5 ms	724 KB	Output is correct
23	Correct	240 ms	20376 KB	Output is correct
24	Correct	256 ms	20380 KB	Output is correct
25	Correct	255 ms	20380 KB	Output is correct
26	Correct	269 ms	19436 KB	Output is correct
27	Correct	246 ms	19412 KB	Output is correct
28	Correct	245 ms	19468 KB	Output is correct
29	Correct	169 ms	19188 KB	Output is correct
30	Correct	169 ms	19248 KB	Output is correct
31	Correct	109 ms	19172 KB	Output is correct
32	Correct	131 ms	21300 KB	Output is correct
33	Correct	217 ms	20188 KB	Output is correct
34	Correct	253 ms	20180 KB	Output is correct
35	Correct	232 ms	20132 KB	Output is correct
36	Correct	211 ms	20052 KB	Output is correct
37	Correct	227 ms	20180 KB	Output is correct
38	Correct	244 ms	20308 KB	Output is correct

Subtask #7

0.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	4 ms	724 KB	Output is correct
14	Correct	4 ms	724 KB	Output is correct
15	Correct	4 ms	724 KB	Output is correct
16	Correct	4 ms	724 KB	Output is correct
17	Correct	4 ms	724 KB	Output is correct
18	Correct	3 ms	808 KB	Output is correct
19	Correct	4 ms	724 KB	Output is correct
20	Correct	4 ms	724 KB	Output is correct
21	Correct	6 ms	852 KB	Output is correct
22	Correct	5 ms	724 KB	Output is correct
23	Correct	953 ms	125724 KB	Output is correct
24	Correct	1047 ms	125708 KB	Output is correct
25	Correct	850 ms	117780 KB	Output is correct
26	Correct	992 ms	124780 KB	Output is correct
27	Correct	985 ms	124772 KB	Output is correct
28	Correct	767 ms	118296 KB	Output is correct
29	Correct	937 ms	118432 KB	Output is correct
30	Correct	798 ms	117896 KB	Output is correct
31	Correct	989 ms	118020 KB	Output is correct
32	Correct	1072 ms	117892 KB	Output is correct
33	Correct	1184 ms	117952 KB	Output is correct
34	Correct	909 ms	118108 KB	Output is correct
35	Correct	933 ms	117968 KB	Output is correct
36	Correct	1520 ms	131448 KB	Output is correct
37	Correct	1422 ms	131444 KB	Output is correct
38	Correct	1483 ms	130896 KB	Output is correct
39	Correct	1537 ms	130868 KB	Output is correct
40	Correct	1302 ms	127532 KB	Output is correct
41	Correct	1332 ms	127532 KB	Output is correct
42	Correct	1100 ms	126332 KB	Output is correct
43	Correct	1078 ms	126024 KB	Output is correct
44	Correct	240 ms	20376 KB	Output is correct
45	Correct	256 ms	20380 KB	Output is correct
46	Correct	255 ms	20380 KB	Output is correct
47	Correct	269 ms	19436 KB	Output is correct
48	Correct	246 ms	19412 KB	Output is correct
49	Correct	245 ms	19468 KB	Output is correct
50	Correct	169 ms	19188 KB	Output is correct
51	Correct	169 ms	19248 KB	Output is correct
52	Correct	109 ms	19172 KB	Output is correct
53	Correct	131 ms	21300 KB	Output is correct
54	Correct	217 ms	20188 KB	Output is correct
55	Correct	253 ms	20180 KB	Output is correct
56	Correct	232 ms	20132 KB	Output is correct
57	Correct	211 ms	20052 KB	Output is correct
58	Correct	227 ms	20180 KB	Output is correct
59	Correct	244 ms	20308 KB	Output is correct
60	Execution timed out	2007 ms	125720 KB	Time limit exceeded
61	Halted	0 ms	0 KB	-