Submission #754980

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
754980	2023-06-09T08:03:15 Z	Zanite	Sequence (APIO23_sequence)	C++17	82 / 100	2000 ms	131540 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;
	int LL = N-l, RL = r+1;

	if (needGreater) {
		int cl = 0, cr = 0;
		if (l > 0) cl = G_Suff.query(0, l).fi - LL + 2*Le.query(l, N-1);
		if (r < N-1) cr = G_Pref.query(r, N-1).fi - 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).se + LL - 2*Gr.query(l, N-1);
		if (r < N-1) cr = L_Pref.query(r, N-1).se + 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); 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	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	0 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	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	0 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	3 ms	724 KB	Output is correct
18	Correct	3 ms	724 KB	Output is correct
19	Correct	4 ms	724 KB	Output is correct
20	Correct	3 ms	724 KB	Output is correct
21	Correct	4 ms	724 KB	Output is correct
22	Correct	4 ms	724 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	1049 ms	125712 KB	Output is correct
3	Correct	1054 ms	125712 KB	Output is correct
4	Correct	871 ms	117884 KB	Output is correct
5	Correct	1018 ms	124764 KB	Output is correct
6	Correct	976 ms	124768 KB	Output is correct
7	Correct	868 ms	118292 KB	Output is correct
8	Correct	906 ms	118432 KB	Output is correct
9	Correct	803 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	982 ms	118004 KB	Output is correct
3	Correct	1022 ms	117896 KB	Output is correct
4	Correct	1062 ms	117888 KB	Output is correct
5	Correct	891 ms	118024 KB	Output is correct
6	Correct	932 ms	117984 KB	Output is correct

Subtask #5

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1500 ms	131440 KB	Output is correct
2	Correct	1506 ms	131540 KB	Output is correct
3	Correct	1588 ms	130868 KB	Output is correct
4	Correct	1483 ms	130972 KB	Output is correct
5	Correct	1288 ms	127560 KB	Output is correct
6	Correct	1375 ms	127528 KB	Output is correct
7	Correct	1123 ms	126332 KB	Output is correct
8	Correct	1153 ms	126112 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	0 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	3 ms	724 KB	Output is correct
18	Correct	3 ms	724 KB	Output is correct
19	Correct	4 ms	724 KB	Output is correct
20	Correct	3 ms	724 KB	Output is correct
21	Correct	4 ms	724 KB	Output is correct
22	Correct	4 ms	724 KB	Output is correct
23	Correct	216 ms	20308 KB	Output is correct
24	Correct	267 ms	20380 KB	Output is correct
25	Correct	243 ms	20376 KB	Output is correct
26	Correct	211 ms	19440 KB	Output is correct
27	Correct	214 ms	19384 KB	Output is correct
28	Correct	202 ms	19468 KB	Output is correct
29	Correct	156 ms	19156 KB	Output is correct
30	Correct	162 ms	19252 KB	Output is correct
31	Correct	108 ms	19180 KB	Output is correct
32	Correct	160 ms	21292 KB	Output is correct
33	Correct	234 ms	20192 KB	Output is correct
34	Correct	209 ms	20208 KB	Output is correct
35	Correct	222 ms	20052 KB	Output is correct
36	Correct	206 ms	20148 KB	Output is correct
37	Correct	229 ms	20244 KB	Output is correct
38	Correct	223 ms	20332 KB	Output is correct

Subtask #7

0.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	0 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	3 ms	724 KB	Output is correct
18	Correct	3 ms	724 KB	Output is correct
19	Correct	4 ms	724 KB	Output is correct
20	Correct	3 ms	724 KB	Output is correct
21	Correct	4 ms	724 KB	Output is correct
22	Correct	4 ms	724 KB	Output is correct
23	Correct	1049 ms	125712 KB	Output is correct
24	Correct	1054 ms	125712 KB	Output is correct
25	Correct	871 ms	117884 KB	Output is correct
26	Correct	1018 ms	124764 KB	Output is correct
27	Correct	976 ms	124768 KB	Output is correct
28	Correct	868 ms	118292 KB	Output is correct
29	Correct	906 ms	118432 KB	Output is correct
30	Correct	803 ms	117896 KB	Output is correct
31	Correct	982 ms	118004 KB	Output is correct
32	Correct	1022 ms	117896 KB	Output is correct
33	Correct	1062 ms	117888 KB	Output is correct
34	Correct	891 ms	118024 KB	Output is correct
35	Correct	932 ms	117984 KB	Output is correct
36	Correct	1500 ms	131440 KB	Output is correct
37	Correct	1506 ms	131540 KB	Output is correct
38	Correct	1588 ms	130868 KB	Output is correct
39	Correct	1483 ms	130972 KB	Output is correct
40	Correct	1288 ms	127560 KB	Output is correct
41	Correct	1375 ms	127528 KB	Output is correct
42	Correct	1123 ms	126332 KB	Output is correct
43	Correct	1153 ms	126112 KB	Output is correct
44	Correct	216 ms	20308 KB	Output is correct
45	Correct	267 ms	20380 KB	Output is correct
46	Correct	243 ms	20376 KB	Output is correct
47	Correct	211 ms	19440 KB	Output is correct
48	Correct	214 ms	19384 KB	Output is correct
49	Correct	202 ms	19468 KB	Output is correct
50	Correct	156 ms	19156 KB	Output is correct
51	Correct	162 ms	19252 KB	Output is correct
52	Correct	108 ms	19180 KB	Output is correct
53	Correct	160 ms	21292 KB	Output is correct
54	Correct	234 ms	20192 KB	Output is correct
55	Correct	209 ms	20208 KB	Output is correct
56	Correct	222 ms	20052 KB	Output is correct
57	Correct	206 ms	20148 KB	Output is correct
58	Correct	229 ms	20244 KB	Output is correct
59	Correct	223 ms	20332 KB	Output is correct
60	Execution timed out	2059 ms	125644 KB	Time limit exceeded
61	Halted	0 ms	0 KB	-