Submission #754985

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
754985	2023-06-09T08:15:28 Z	Zanite	Sequence (APIO23_sequence)	C++17	100 / 100	1834 ms	100180 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	= int;
	Elm DEFAULT = -iINF;

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

	int sz;
	vector<Elm> seg, lazy;

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

	#define updateNode(pos, val) seg[pos] += val, lazy[pos] += val
	#define merge(a, b) max(a, b)

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

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

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

	void update(int pos, int l, int r, int ul, int ur, Elm val) {
		if (l > r || ul > ur || ul > r || l > ur) {return;}
		if (ul <= l && r <= ur) {
			updateNode(pos, 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, 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;
	int LL = N-l, RL = r+1;

	if (needGreater) {
		int cl = 0, cr = 0;
		if (l > 0) cl = G_Suff.query(0, l) - LL + 2*Le.query(l, N-1);
		if (r < N-1) cr = G_Pref.query(r, N-1) - RL + 2*Le.query(0, r);

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

		cur = max(cur, cl + cr);
		
	} else {
		int cl = 0, cr = 0;
		if (l > 0) cl = L_Suff.query(0, l) - LL + 2*Gr.query(l, N-1);
		if (r < N-1) cr = L_Pref.query(r, N-1) - RL + 2*Gr.query(0, r);

		// 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);
	Reverse(init);
	G_Suff.build(init);

	for (auto &i : init) i *= -1;
	L_Suff.build(init);
	Reverse(init);
	L_Pref.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	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 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	0 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	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 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	0 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	3 ms	596 KB	Output is correct
14	Correct	4 ms	596 KB	Output is correct
15	Correct	4 ms	596 KB	Output is correct
16	Correct	3 ms	648 KB	Output is correct
17	Correct	3 ms	596 KB	Output is correct
18	Correct	3 ms	596 KB	Output is correct
19	Correct	3 ms	596 KB	Output is correct
20	Correct	3 ms	640 KB	Output is correct
21	Correct	4 ms	724 KB	Output is correct
22	Correct	3 ms	596 KB	Output is correct

Subtask #3

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	871 ms	94292 KB	Output is correct
3	Correct	870 ms	94408 KB	Output is correct
4	Correct	736 ms	86712 KB	Output is correct
5	Correct	870 ms	93464 KB	Output is correct
6	Correct	844 ms	93400 KB	Output is correct
7	Correct	722 ms	86980 KB	Output is correct
8	Correct	740 ms	87108 KB	Output is correct
9	Correct	721 ms	86496 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	828 ms	86736 KB	Output is correct
3	Correct	862 ms	86580 KB	Output is correct
4	Correct	848 ms	86588 KB	Output is correct
5	Correct	766 ms	86816 KB	Output is correct
6	Correct	774 ms	86664 KB	Output is correct

Subtask #5

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1275 ms	100136 KB	Output is correct
2	Correct	1211 ms	100124 KB	Output is correct
3	Correct	1218 ms	99556 KB	Output is correct
4	Correct	1215 ms	99556 KB	Output is correct
5	Correct	1072 ms	96332 KB	Output is correct
6	Correct	1058 ms	96280 KB	Output is correct
7	Correct	936 ms	95120 KB	Output is correct
8	Correct	901 ms	94924 KB	Output is correct

Subtask #6

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 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	0 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	3 ms	596 KB	Output is correct
14	Correct	4 ms	596 KB	Output is correct
15	Correct	4 ms	596 KB	Output is correct
16	Correct	3 ms	648 KB	Output is correct
17	Correct	3 ms	596 KB	Output is correct
18	Correct	3 ms	596 KB	Output is correct
19	Correct	3 ms	596 KB	Output is correct
20	Correct	3 ms	640 KB	Output is correct
21	Correct	4 ms	724 KB	Output is correct
22	Correct	3 ms	596 KB	Output is correct
23	Correct	188 ms	15476 KB	Output is correct
24	Correct	185 ms	15316 KB	Output is correct
25	Correct	187 ms	15384 KB	Output is correct
26	Correct	175 ms	14540 KB	Output is correct
27	Correct	174 ms	14432 KB	Output is correct
28	Correct	178 ms	14420 KB	Output is correct
29	Correct	134 ms	14192 KB	Output is correct
30	Correct	132 ms	14256 KB	Output is correct
31	Correct	91 ms	14232 KB	Output is correct
32	Correct	116 ms	16292 KB	Output is correct
33	Correct	184 ms	15192 KB	Output is correct
34	Correct	193 ms	15200 KB	Output is correct
35	Correct	187 ms	15088 KB	Output is correct
36	Correct	199 ms	15144 KB	Output is correct
37	Correct	183 ms	15160 KB	Output is correct
38	Correct	186 ms	15328 KB	Output is correct

Subtask #7

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 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	0 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	3 ms	596 KB	Output is correct
14	Correct	4 ms	596 KB	Output is correct
15	Correct	4 ms	596 KB	Output is correct
16	Correct	3 ms	648 KB	Output is correct
17	Correct	3 ms	596 KB	Output is correct
18	Correct	3 ms	596 KB	Output is correct
19	Correct	3 ms	596 KB	Output is correct
20	Correct	3 ms	640 KB	Output is correct
21	Correct	4 ms	724 KB	Output is correct
22	Correct	3 ms	596 KB	Output is correct
23	Correct	871 ms	94292 KB	Output is correct
24	Correct	870 ms	94408 KB	Output is correct
25	Correct	736 ms	86712 KB	Output is correct
26	Correct	870 ms	93464 KB	Output is correct
27	Correct	844 ms	93400 KB	Output is correct
28	Correct	722 ms	86980 KB	Output is correct
29	Correct	740 ms	87108 KB	Output is correct
30	Correct	721 ms	86496 KB	Output is correct
31	Correct	828 ms	86736 KB	Output is correct
32	Correct	862 ms	86580 KB	Output is correct
33	Correct	848 ms	86588 KB	Output is correct
34	Correct	766 ms	86816 KB	Output is correct
35	Correct	774 ms	86664 KB	Output is correct
36	Correct	1275 ms	100136 KB	Output is correct
37	Correct	1211 ms	100124 KB	Output is correct
38	Correct	1218 ms	99556 KB	Output is correct
39	Correct	1215 ms	99556 KB	Output is correct
40	Correct	1072 ms	96332 KB	Output is correct
41	Correct	1058 ms	96280 KB	Output is correct
42	Correct	936 ms	95120 KB	Output is correct
43	Correct	901 ms	94924 KB	Output is correct
44	Correct	188 ms	15476 KB	Output is correct
45	Correct	185 ms	15316 KB	Output is correct
46	Correct	187 ms	15384 KB	Output is correct
47	Correct	175 ms	14540 KB	Output is correct
48	Correct	174 ms	14432 KB	Output is correct
49	Correct	178 ms	14420 KB	Output is correct
50	Correct	134 ms	14192 KB	Output is correct
51	Correct	132 ms	14256 KB	Output is correct
52	Correct	91 ms	14232 KB	Output is correct
53	Correct	116 ms	16292 KB	Output is correct
54	Correct	184 ms	15192 KB	Output is correct
55	Correct	193 ms	15200 KB	Output is correct
56	Correct	187 ms	15088 KB	Output is correct
57	Correct	199 ms	15144 KB	Output is correct
58	Correct	183 ms	15160 KB	Output is correct
59	Correct	186 ms	15328 KB	Output is correct
60	Correct	1792 ms	94408 KB	Output is correct
61	Correct	1787 ms	94396 KB	Output is correct
62	Correct	1732 ms	94416 KB	Output is correct
63	Correct	1549 ms	87668 KB	Output is correct
64	Correct	1539 ms	87664 KB	Output is correct
65	Correct	1506 ms	87636 KB	Output is correct
66	Correct	901 ms	86784 KB	Output is correct
67	Correct	905 ms	86856 KB	Output is correct
68	Correct	646 ms	86576 KB	Output is correct
69	Correct	804 ms	100180 KB	Output is correct
70	Correct	1644 ms	93384 KB	Output is correct
71	Correct	1629 ms	93296 KB	Output is correct
72	Correct	1563 ms	92852 KB	Output is correct
73	Correct	1787 ms	93156 KB	Output is correct
74	Correct	1834 ms	92744 KB	Output is correct
75	Correct	1793 ms	93120 KB	Output is correct