Submission #754978

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
754978	2023-06-09T07:55:58 Z	Zanite	Sequence (APIO23_sequence)	C++17	82 / 100	2000 ms	131644 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);
		
	} else {
		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	324 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	324 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	852 KB	Output is correct
14	Correct	4 ms	724 KB	Output is correct
15	Correct	5 ms	724 KB	Output is correct
16	Correct	5 ms	724 KB	Output is correct
17	Correct	4 ms	724 KB	Output is correct
18	Correct	3 ms	816 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	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	1 ms	212 KB	Output is correct
2	Correct	1101 ms	125720 KB	Output is correct
3	Correct	1218 ms	125716 KB	Output is correct
4	Correct	1070 ms	117888 KB	Output is correct
5	Correct	1184 ms	124752 KB	Output is correct
6	Correct	1180 ms	124836 KB	Output is correct
7	Correct	990 ms	118288 KB	Output is correct
8	Correct	1073 ms	118436 KB	Output is correct
9	Correct	973 ms	117996 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	1199 ms	118016 KB	Output is correct
3	Correct	1199 ms	117896 KB	Output is correct
4	Correct	1310 ms	117892 KB	Output is correct
5	Correct	1089 ms	118032 KB	Output is correct
6	Correct	1155 ms	117984 KB	Output is correct

Subtask #5

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1699 ms	131644 KB	Output is correct
2	Correct	1701 ms	131400 KB	Output is correct
3	Correct	1699 ms	130868 KB	Output is correct
4	Correct	1759 ms	130864 KB	Output is correct
5	Correct	1471 ms	127536 KB	Output is correct
6	Correct	1520 ms	127536 KB	Output is correct
7	Correct	1281 ms	126324 KB	Output is correct
8	Correct	1306 ms	126100 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	324 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	852 KB	Output is correct
14	Correct	4 ms	724 KB	Output is correct
15	Correct	5 ms	724 KB	Output is correct
16	Correct	5 ms	724 KB	Output is correct
17	Correct	4 ms	724 KB	Output is correct
18	Correct	3 ms	816 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	724 KB	Output is correct
22	Correct	5 ms	724 KB	Output is correct
23	Correct	283 ms	20380 KB	Output is correct
24	Correct	301 ms	20504 KB	Output is correct
25	Correct	264 ms	20332 KB	Output is correct
26	Correct	257 ms	19456 KB	Output is correct
27	Correct	266 ms	19444 KB	Output is correct
28	Correct	269 ms	19468 KB	Output is correct
29	Correct	198 ms	19156 KB	Output is correct
30	Correct	204 ms	19252 KB	Output is correct
31	Correct	118 ms	19228 KB	Output is correct
32	Correct	162 ms	21288 KB	Output is correct
33	Correct	261 ms	20192 KB	Output is correct
34	Correct	309 ms	20180 KB	Output is correct
35	Correct	312 ms	20136 KB	Output is correct
36	Correct	294 ms	20260 KB	Output is correct
37	Correct	262 ms	20168 KB	Output is correct
38	Correct	272 ms	20180 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	324 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	852 KB	Output is correct
14	Correct	4 ms	724 KB	Output is correct
15	Correct	5 ms	724 KB	Output is correct
16	Correct	5 ms	724 KB	Output is correct
17	Correct	4 ms	724 KB	Output is correct
18	Correct	3 ms	816 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	724 KB	Output is correct
22	Correct	5 ms	724 KB	Output is correct
23	Correct	1101 ms	125720 KB	Output is correct
24	Correct	1218 ms	125716 KB	Output is correct
25	Correct	1070 ms	117888 KB	Output is correct
26	Correct	1184 ms	124752 KB	Output is correct
27	Correct	1180 ms	124836 KB	Output is correct
28	Correct	990 ms	118288 KB	Output is correct
29	Correct	1073 ms	118436 KB	Output is correct
30	Correct	973 ms	117996 KB	Output is correct
31	Correct	1199 ms	118016 KB	Output is correct
32	Correct	1199 ms	117896 KB	Output is correct
33	Correct	1310 ms	117892 KB	Output is correct
34	Correct	1089 ms	118032 KB	Output is correct
35	Correct	1155 ms	117984 KB	Output is correct
36	Correct	1699 ms	131644 KB	Output is correct
37	Correct	1701 ms	131400 KB	Output is correct
38	Correct	1699 ms	130868 KB	Output is correct
39	Correct	1759 ms	130864 KB	Output is correct
40	Correct	1471 ms	127536 KB	Output is correct
41	Correct	1520 ms	127536 KB	Output is correct
42	Correct	1281 ms	126324 KB	Output is correct
43	Correct	1306 ms	126100 KB	Output is correct
44	Correct	283 ms	20380 KB	Output is correct
45	Correct	301 ms	20504 KB	Output is correct
46	Correct	264 ms	20332 KB	Output is correct
47	Correct	257 ms	19456 KB	Output is correct
48	Correct	266 ms	19444 KB	Output is correct
49	Correct	269 ms	19468 KB	Output is correct
50	Correct	198 ms	19156 KB	Output is correct
51	Correct	204 ms	19252 KB	Output is correct
52	Correct	118 ms	19228 KB	Output is correct
53	Correct	162 ms	21288 KB	Output is correct
54	Correct	261 ms	20192 KB	Output is correct
55	Correct	309 ms	20180 KB	Output is correct
56	Correct	312 ms	20136 KB	Output is correct
57	Correct	294 ms	20260 KB	Output is correct
58	Correct	262 ms	20168 KB	Output is correct
59	Correct	272 ms	20180 KB	Output is correct
60	Execution timed out	2069 ms	125640 KB	Time limit exceeded
61	Halted	0 ms	0 KB	-