oj.uz

Submission #199371

# Submission time Handle Problem Language Result Execution time Memory
199371 2020-01-31T19:07:03 Z Benq Palindromes (APIO14_palindrome) C++14
100 / 100
 118 ms 75052 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 

typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<ld,ld> pd; 
#define mp make_pair 
#define f first
#define s second

typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<ld> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353; // = (119<<23)+1
const int MX = 2e5+5;
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 

template<class T> bool ckmin(T& a, const T& b) { 
	return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; }
int pc(int x) { return __builtin_popcount(x); } 

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, 
	rb_tree_tag, tree_order_statistics_node_update>; 
// change null_type for map
#define ook order_of_key
#define fbo find_by_order

void treeExample() {
	Tree<int> t, t2; t.insert(8);
	auto it = t.insert(10).f; assert(it == t.lb(9));
	assert(t.ook(10) == 1); assert(t.ook(11) == 2);
	assert(*t.fbo(0) == 8);
	t.join(t2); // assuming T < T2 or T > T2, merge t2 into t
}

namespace input {
	template<class T> void re(complex<T>& x);
	template<class T1, class T2> void re(pair<T1,T2>& p);
	template<class T> void re(vector<T>& a);
	template<class T, size_t SZ> void re(array<T,SZ>& a);

	template<class T> void re(T& x) { cin >> x; }
	void re(double& x) { string t; re(t); x = stod(t); }
	void re(ld& x) { string t; re(t); x = stold(t); }
	template<class T, class... Ts> void re(T& t, Ts&... ts) { 
		re(t); re(ts...); 
	}

	template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = {a,b}; }
	template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); }
	template<class T> void re(vector<T>& a) { F0R(i,sz(a)) re(a[i]); }
	template<class T, size_t SZ> void re(array<T,SZ>& a) { F0R(i,SZ) re(a[i]); }
}

using namespace input;

namespace output {
	void pr(int x) { cout << x; }
	void pr(long x) { cout << x; }
	void pr(ll x) { cout << x; }
	void pr(unsigned x) { cout << x; }
	void pr(unsigned long x) { cout << x; }
	void pr(unsigned long long x) { cout << x; }
	void pr(float x) { cout << x; }
	void pr(double x) { cout << x; }
	void pr(ld x) { cout << x; }
	void pr(char x) { cout << x; }
	void pr(const char* x) { cout << x; }
	void pr(const string& x) { cout << x; }
	void pr(bool x) { pr(x ? "true" : "false"); }
	template<class T> void pr(const complex<T>& x) { cout << x; }
	
	template<class T1, class T2> void pr(const pair<T1,T2>& x);
	template<class T> void pr(const T& x);
	
	template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
		pr(t); pr(ts...); 
	}
	template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
		pr("{",x.f,", ",x.s,"}"); 
	}
	template<class T> void pr(const T& x) { 
		pr("{"); // const iterator needed for vector<bool>
		bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
		pr("}");
	}
	
	void ps() { pr("\n"); } // print w/ spaces
	template<class T, class... Ts> void ps(const T& t, const Ts&... ts) { 
		pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); 
	}
	
	void pc() { pr("]\n"); } // debug w/ commas
	template<class T, class... Ts> void pc(const T& t, const Ts&... ts) { 
		pr(t); if (sizeof...(ts)) pr(", "); pc(ts...); 
	}
	#define dbg(x...) pr("[",#x,"] = ["), pc(x);
}

using namespace output;

namespace io {
	void setIn(string s) { freopen(s.c_str(),"r",stdin); }
	void setOut(string s) { freopen(s.c_str(),"w",stdout); }
	void setIO(string s = "") {
		ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O
		// cin.exceptions(cin.failbit); 
		// throws exception when do smth illegal
		// ex. try to read letter into int
		if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
	}
}

using namespace io;

struct mi {
	typedef decay<decltype(MOD)>::type T; 
 	/// don't silently convert to T
	T v; explicit operator T() const { return v; }
	mi() { v = 0; }
	mi(ll _v) { 
		v = (-MOD < _v && _v < MOD) ? _v : _v % MOD;
		if (v < 0) v += MOD;
	}
	friend bool operator==(const mi& a, const mi& b) { 
		return a.v == b.v; }
	friend bool operator!=(const mi& a, const mi& b) { 
		return !(a == b); }
	friend bool operator<(const mi& a, const mi& b) { 
		return a.v < b.v; }
	friend void re(mi& a) { ll x; re(x); a = mi(x); }
	friend void pr(const mi& a) { pr(a.v); }
	friend ostream& operator<<(ostream& os, const mi& a) { 
		return os << a.v; }
   
	mi& operator+=(const mi& m) { 
		if ((v += m.v) >= MOD) v -= MOD; 
		return *this; }
	mi& operator-=(const mi& m) { 
		if ((v -= m.v) < 0) v += MOD; 
		return *this; }
	mi& operator*=(const mi& m) { 
		v = (ll)v*m.v%MOD; return *this; }
	mi& operator/=(const mi& m) { return (*this) *= inv(m); }
	friend mi pow(mi a, ll p) {
		mi ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans;
	}
	friend mi inv(const mi& a) { assert(a.v != 0); 
		return pow(a,MOD-2); }
		
	mi operator-() const { return mi(-v); }
	mi& operator++() { return *this += 1; }
	mi& operator--() { return *this -= 1; }
	friend mi operator+(mi a, const mi& b) { return a += b; }
	friend mi operator-(mi a, const mi& b) { return a -= b; }
	friend mi operator*(mi a, const mi& b) { return a *= b; }
	friend mi operator/(mi a, const mi& b) { return a /= b; }
};
typedef vector<mi> vmi;
typedef pair<mi,mi> pmi;
typedef vector<pmi> vpmi;

vector<vmi> comb;
void genComb(int SZ) {
	comb.assign(SZ,vmi(SZ)); comb[0][0] = 1;
	FOR(i,1,SZ) F0R(j,i+1) 
		comb[i][j] = comb[i-1][j]+(j?comb[i-1][j-1]:0);
}

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

struct PalTree {
	static const int ASZ = 26;
	struct node {
		array<int,ASZ> to = array<int,ASZ>();
		int len, link, oc = 0;
		int slink = 0, diff = 0;
		array<int,2> seriesAns;
		node(int _len, int _link) : len(_len), link(_link) {}
	};
	str s; vector<array<int,2>> ans;
	vector<node> d;
	int last = 1;
	PalTree() { 
		s += '@'; ans.pb({0,MOD});
		d.eb(0,1); d.eb(-1,0); 
	}
	int getLink(int v) {
		while (s[sz(s)-d[v].len-2] != s.bk) v = d[v].link;
		return v;
	}
	void updAns() { // serial path has O(log n) vertices
		ans.pb({MOD,MOD});
		for (int v = last; d[v].len > 0; v = d[v].slink) {
			d[v].seriesAns = ans[sz(s)-1-(d[d[v].slink].len+d[v].diff)];
			if (d[v].diff == d[d[v].link].diff) 
				F0R(i,2) ckmin(d[v].seriesAns[i],d[d[v].link].seriesAns[i]);
			// previous oc of link[v] = start of last oc of v
			F0R(i,2) ckmin(ans.bk[i],d[v].seriesAns[i^1]+1);
		}
	}
	void addChar(char C) {
		s += C; int c = C-'a'; last = getLink(last);
		if (!d[last].to[c]) {
			d.eb(d[last].len+2,d[getLink(d[last].link)].to[c]);
			d[last].to[c] = sz(d)-1;
			auto& z = d.bk; z.diff = z.len-d[z.link].len;
			z.slink = z.diff == d[z.link].diff 
				? d[z.link].slink : z.link;
			// slink[v] = max suffix u of v such that 
			// diff[v] != diff[u]
		}
		last = d[last].to[c]; d[last].oc ++;
		updAns();
	}
	void numOc() { // # occurrences of each palindrome
		ROF(i,2,sz(d)) d[d[i].link].oc += d[i].oc;
	}
};
 
PalTree p;
 
int nor(int x) {
	return x == MOD ? -1 : x;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	str s; 
	// F0R(i,500) s += char('a'+(rand()%26));
	re(s); 
	trav(c,s) {
		p.addChar(c);
		// ps(nor(p.ans.bk[1]),nor(p.ans.bk[0]));
	}
	p.numOc(); ll ans = 0;
	FOR(i,2,sz(p.d)) ckmax(ans,(ll)p.d[i].len*p.d[i].oc);
	ps(ans);
}
 
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Compilation message

palindrome.cpp: In function 'void io::setIn(std::__cxx11::string)':
palindrome.cpp:139:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
palindrome.cpp: In function 'void io::setOut(std::__cxx11::string)':
palindrome.cpp:140:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 6 ms 380 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 248 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct
23 Correct 5 ms 380 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Correct 5 ms 376 KB Output is correct
28 Correct 5 ms 376 KB Output is correct
29 Correct 5 ms 376 KB Output is correct
30 Correct 5 ms 376 KB Output is correct
31 Correct 5 ms 376 KB Output is correct
32 Correct 5 ms 380 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2640 KB Output is correct
2 Correct 8 ms 2636 KB Output is correct
3 Correct 7 ms 2764 KB Output is correct
4 Correct 8 ms 2640 KB Output is correct
5 Correct 8 ms 2640 KB Output is correct
6 Correct 8 ms 2640 KB Output is correct
7 Correct 7 ms 2636 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 6 ms 632 KB Output is correct
10 Correct 7 ms 1508 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 18516 KB Output is correct
2 Correct 29 ms 18516 KB Output is correct
3 Correct 28 ms 18644 KB Output is correct
4 Correct 29 ms 18516 KB Output is correct
5 Correct 38 ms 18516 KB Output is correct
6 Correct 29 ms 19156 KB Output is correct
7 Correct 31 ms 19156 KB Output is correct
8 Correct 10 ms 1968 KB Output is correct
9 Correct 14 ms 6060 KB Output is correct
10 Correct 33 ms 19156 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 72492 KB Output is correct
2 Correct 90 ms 74956 KB Output is correct
3 Correct 88 ms 72780 KB Output is correct
4 Correct 92 ms 72756 KB Output is correct
5 Correct 118 ms 72752 KB Output is correct
6 Correct 91 ms 75052 KB Output is correct
7 Correct 65 ms 39624 KB Output is correct
8 Correct 20 ms 6004 KB Output is correct
9 Correct 20 ms 6132 KB Output is correct
10 Correct 80 ms 39088 KB Output is correct
11 Correct 84 ms 72876 KB Output is correct
12 Correct 27 ms 10088 KB Output is correct