Submission #754973

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
754973	2023-06-09T07:42:06 Z	Zanite	Sequence (APIO23_sequence)	C++17	69 / 100	2000 ms	131396 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);

		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	0 ms	212 KB	Output is correct
2	Correct	1 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	0 ms	212 KB	Output is correct
2	Correct	1 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	7 ms	724 KB	Output is correct
14	Correct	6 ms	724 KB	Output is correct
15	Correct	7 ms	724 KB	Output is correct
16	Correct	7 ms	724 KB	Output is correct
17	Correct	7 ms	724 KB	Output is correct
18	Correct	4 ms	724 KB	Output is correct
19	Correct	5 ms	724 KB	Output is correct
20	Correct	5 ms	724 KB	Output is correct
21	Correct	5 ms	724 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	0 ms	212 KB	Output is correct
2	Correct	1498 ms	125720 KB	Output is correct
3	Correct	1536 ms	125712 KB	Output is correct
4	Correct	1403 ms	117888 KB	Output is correct
5	Correct	1497 ms	124776 KB	Output is correct
6	Correct	1417 ms	124776 KB	Output is correct
7	Correct	1340 ms	118300 KB	Output is correct
8	Correct	1429 ms	118432 KB	Output is correct
9	Correct	1266 ms	117900 KB	Output is correct

Subtask #4

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1639 ms	118032 KB	Output is correct
3	Correct	1700 ms	117892 KB	Output is correct
4	Correct	1836 ms	117892 KB	Output is correct
5	Correct	1640 ms	118024 KB	Output is correct
6	Correct	1642 ms	117976 KB	Output is correct

Subtask #5

0.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2078 ms	131396 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 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	7 ms	724 KB	Output is correct
14	Correct	6 ms	724 KB	Output is correct
15	Correct	7 ms	724 KB	Output is correct
16	Correct	7 ms	724 KB	Output is correct
17	Correct	7 ms	724 KB	Output is correct
18	Correct	4 ms	724 KB	Output is correct
19	Correct	5 ms	724 KB	Output is correct
20	Correct	5 ms	724 KB	Output is correct
21	Correct	5 ms	724 KB	Output is correct
22	Correct	5 ms	724 KB	Output is correct
23	Correct	371 ms	20388 KB	Output is correct
24	Correct	373 ms	20428 KB	Output is correct
25	Correct	369 ms	20428 KB	Output is correct
26	Correct	392 ms	19532 KB	Output is correct
27	Correct	397 ms	19448 KB	Output is correct
28	Correct	429 ms	19540 KB	Output is correct
29	Correct	286 ms	19276 KB	Output is correct
30	Correct	289 ms	19256 KB	Output is correct
31	Correct	145 ms	19236 KB	Output is correct
32	Correct	194 ms	21292 KB	Output is correct
33	Correct	384 ms	20180 KB	Output is correct
34	Correct	340 ms	20204 KB	Output is correct
35	Correct	368 ms	20172 KB	Output is correct
36	Correct	379 ms	20152 KB	Output is correct
37	Correct	346 ms	20168 KB	Output is correct
38	Correct	356 ms	20200 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	1 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	7 ms	724 KB	Output is correct
14	Correct	6 ms	724 KB	Output is correct
15	Correct	7 ms	724 KB	Output is correct
16	Correct	7 ms	724 KB	Output is correct
17	Correct	7 ms	724 KB	Output is correct
18	Correct	4 ms	724 KB	Output is correct
19	Correct	5 ms	724 KB	Output is correct
20	Correct	5 ms	724 KB	Output is correct
21	Correct	5 ms	724 KB	Output is correct
22	Correct	5 ms	724 KB	Output is correct
23	Correct	1498 ms	125720 KB	Output is correct
24	Correct	1536 ms	125712 KB	Output is correct
25	Correct	1403 ms	117888 KB	Output is correct
26	Correct	1497 ms	124776 KB	Output is correct
27	Correct	1417 ms	124776 KB	Output is correct
28	Correct	1340 ms	118300 KB	Output is correct
29	Correct	1429 ms	118432 KB	Output is correct
30	Correct	1266 ms	117900 KB	Output is correct
31	Correct	1639 ms	118032 KB	Output is correct
32	Correct	1700 ms	117892 KB	Output is correct
33	Correct	1836 ms	117892 KB	Output is correct
34	Correct	1640 ms	118024 KB	Output is correct
35	Correct	1642 ms	117976 KB	Output is correct
36	Execution timed out	2078 ms	131396 KB	Time limit exceeded
37	Halted	0 ms	0 KB	-