Submission #259071

#	Time	Username	Problem	Language	Result	Execution time	Memory
259071		pure_mem	Palindromes (APIO14_palindrome)	C++17	73 / 100	1086 ms	55184 KiB

palindrome

#include <bits/stdc++.h>
 
#define ll long long
#define X first
#define Y second
#define MP make_pair
 
using namespace std;
 
const int N = 3e5 + 3;
 
struct sarr{
	ll mod1 = 1e9 + 7, mod2 = 1e9 + 9, mod3 = 1e9 + 21;
	ll pr1[N], pr2[N], pr3[N];
	ll hs1[N], hs2[N], hs3[N], rhs1[N], rhs2[N], rhs3[N];
	int sf[N], poses[N], lcm[N], sp[19][N], lg[N];
	string s;
 
	unordered_map< ll, bool > were;
 
	void init(string temp){
		s = temp;
		pr1[0] = pr2[0] = pr3[0] = 1;
		lg[1] = 0;
		for(int i = 1;i < N;i++){
			pr1[i] = pr1[i - 1] * 29 % mod1;
			pr2[i] = pr2[i - 1] * 31 % mod2;
		//	pr3[i] = pr3[i - 1] * 37 % mod3;
			if(i > 1)
				lg[i] = lg[i / 2] + 1;
		}
		for(int i = 0;i < (int)temp.size();i++){
			sf[i + 1] = i + 1;
			hs1[i + 1] = (hs1[i] + (temp[i] - 'a' + 1) * pr1[i]) % mod1;
			hs2[i + 1] = (hs2[i] + (temp[i] - 'a' + 1) * pr2[i]) % mod2;
		//	hs3[i + 1] = (hs3[i] + (temp[i] - 'a' + 1) * pr3[i]) % mod3;	
		}
		for(int i = 0;i < (int)temp.size();i++){
			int j = (int)temp.size() - i - 1;
			rhs1[j + 1] = (rhs1[j + 2] + (temp[j] - 'a' + 1) * pr1[i]) % mod1;
			rhs2[j + 1] = (rhs2[j + 2] + (temp[j] - 'a' + 1) * pr2[i]) % mod2;
	//		rhs3[j + 1] = (rhs3[j + 2] + (temp[j] - 'a' + 1) * pr3[i]) % mod3;	
		}
		this->build_sf();
		for(int i = 1;i < (int)temp.size();i++){
			lcm[i] = this->get_lcm(sf[i], sf[i + 1]);
		//	cerr << lcm[i] << " ";
		}
		//cerr << endl;
		for(int i = 1;i <= (int)temp.size();i++){
			sp[0][i] = lcm[i];
		//	cerr << sf[i] << " ";
			poses[sf[i]] = i;
		}
		for(int i = 1;i < 19;i++){
			for(int j = 1;j + (1 << i) - 1 <= (int)temp.size();j++){
				sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
			}
		}
	}

	void build_sf(){
		string temp = s;
		temp += "#"; 
		int n = temp.size();
		vector<int> cl(n, 0), pn(n, 0), cn(n, 0), p(n, 0), cnt(n, 0);
		for(int i = 0;i < n;i++)
			p[i] = i;
		sort(p.begin(), p.end(), [this](int x, int y){
			if(s[x] < s[y])
				return 1;
			return 0;
		});
		int classes = 0;
		for(int i = 1;i < n;i++){
			if(s[p[i]] != s[p[i - 1]])
				classes++;
			cl[p[i]] = classes;
		}
		for(int it = 0;(1 << it) < n;it++){
			for(int i = 0;i < n;i++){
				pn[i] = p[i] - (1 << it);
				if(pn[i] < 0)
					pn[i] += n;
			}
			memset(&cnt[0], 0, sizeof(cnt[0]) * cnt.size());
		//	memset(cnt, 0, sizeof(cnt));
			//cnt.assign(cnt.size(), 0);
			for(int i = 0;i < n;i++){
				++cnt[cl[pn[i]]];
			}
			for(int i = 1;i <= classes;i++){
				cnt[i] += cnt[i - 1];	
			}
			for(int i = n - 1;i >= 0;i--){
				p[--cnt[cl[pn[i]]]] = pn[i];
			}
			cn[p[0]] = 0;
			classes = 0;
			for(int i = 1;i < n;i++){
				int m1 = (p[i] + (1 << it)) % n, m2 = (p[i - 1] + (1 << it)) % n;
				if(cl[p[i]] != cl[p[i - 1]] || cl[m1] != cl[m2])
					classes++;
				cn[p[i]] = classes;
			}
			cl.swap(cn);
			//for(int i = 0;i < n;i++)
			//	cl[i] = cn[i];
		}
		for(int i = 2;i <= n;i++){
			sf[i - 1] = p[i - 1] + 1;	
		}
	}
 
	bool check(int l, int r){
		bool can = 1;
	//	return can;
		ll add1 = 0, add2 = 0;
		if(l > (int)s.size() - r + 1)
			add2 = l - ((int)s.size() - r + 1);
		else
			add1 = (int)s.size() - r + 1 - l;
		if((hs1[r] - hs1[l - 1] + mod1) % mod1 * pr1[add1] % mod1 != (rhs1[l] - rhs1[r + 1] + mod1) % mod1 * pr1[add2] % mod1)
			can = 0;
		if((hs2[r] - hs2[l - 1] + mod2) % mod2 * pr2[add1] % mod2 != (rhs2[l] - rhs2[r + 1] + mod2) % mod2 * pr2[add2] % mod2)
			can = 0;
		//if((hs3[r] - hs3[l - 1] + mod3) % mod3 * pr3[add1] % mod3 != (rhs3[l] - rhs3[r + 1] + mod3) % mod3 * pr3[add2] % mod3)
		//	can = 0;
		return can;
	}
 
	bool check_eq(int l1, int r1, int l2, int r2){
		bool can = 1;
		if(l1 > l2)
			swap(l1, l2), swap(r1, r2);
		if(((hs1[r1] - hs1[l1 - 1] + mod1) % mod1) * pr1[l2 - l1] % mod1 != (hs1[r2] - hs1[l2 - 1] + mod1) % mod1)
			can = 0;
		if(((hs2[r1] - hs2[l1 - 1] + mod2) % mod2) * pr2[l2 - l1] % mod2 != (hs2[r2] - hs2[l2 - 1] + mod2) % mod2)
			can = 0;
		//if(((hs3[r1] - hs3[l1 - 1] + mod3) % mod3) * pr3[l2 - l1] % mod3 != (hs3[r2] - hs3[l2 - 1] + mod3) % mod3)
		//	can = 0;
		return can;
	}
 
	int get_lcm(int l, int r){
		if(l > r)
			swap(l, r);
		int tl = 1, tr = (int)s.size() - r + 1, tp = 0;
		while(tl <= tr){
			int tm = (tl + tr) / 2;
			if(this->check_eq(l, l + tm - 1, r, r + tm - 1))
				tl = tm + 1, tp = tm;
			else
				tr = tm - 1;
		}
		return tp;
	}
 
	bool is_less(int l, int r){
		int lc = this->get_lcm(l, r);
		if(l + lc - 1 == (int)s.size())
			return 1;
		else if(r + lc - 1 == (int)s.size())
			return 0;
		return s[l + lc - 1] < s[r + lc - 1];
	}
 
	bool is_were(int l, int r){
		ll hash1 = ((hs1[r] - hs1[l - 1] + mod1) % mod1) * pr1[(int)s.size() - l] % mod1;
		ll hash2 = ((hs2[r] - hs2[l - 1] + mod2) % mod2) * pr2[(int)s.size() - l] % mod2;
		hash1 = hash1 + hash2 * mod3;
		//ll hash3 = ((hs3[r] - hs3[l - 1] + mod3) % mod3) * pr3[(int)s.size() - l] % mod3;
		if(were.count(hash1))
			return 0;
		were[hash1] = 1;
		return 1;
	}
 
	int lcm_min(int l, int r){
		if(l == r)
			return (int)s.size() - l + 1;
		r -= 1;
		int lens = (r - l + 1);
		//cerr << lg[lens] << " " << lens << " " << sp[lg[lens]][l] << "s\n";
		return min(sp[lg[lens]][l], sp[lg[lens]][r - (1 << lg[lens]) + 1]);	
	}
 
	int get_cnt(int l, int r){
		int idx = poses[l];
		int tl = 1, tr = idx - 1, res = 1;
		while(tl <= tr){
			int tm = (tl + tr) / 2;
			if(this->lcm_min(tm, idx) >= r - l + 1){
				tr = tm - 1, res = idx - tm + 1;
			}
			else{
				tl = tm + 1;
			}
		}
		//int tp = 1;
		tl = idx + 1, tr = (int)s.size();
		while(tl <= tr){
			int tm = (tl + tr) / 2;
			if(this->lcm_min(idx, tm) >= r - l + 1){
				tl = tm + 1;
			}
			else{
				tr = tm - 1;
			}
		}
	//	cerr << res << " " << tp << "\n";
		return res + (tl - idx) - 1;
	}
}g;

int d1[N], d2[N];

void manachar(){
 	int l = 0, r = -1;
 	int n = g.s.size();
 	for(int i = 0;i < n;i++){
 		int k = (i > r ? 1: min(d1[l + r - i], r - i + 1));
 		while(k + i < n && i - k >= 0 && g.s[i + k] == g.s[i - k])k++;
 		d1[i] = k;
 		if(i + k - 1 > r)
 			l = i - k + 1, r = i + k - 1;
 	}
 	l = 0, r = -1;
 	for(int i = 0;i < n;i++){
 		int k = (i > r ? 0: min(d1[l + r - i + 1], r - i + 1));
 		while(k + i < n && i - k - 1 >= 0 && g.s[i + k] == g.s[i - k - 1])k++;
 		d2[i] = k;
 		if(i + k - 1 > r)
 			l = i - k, r = i + k - 1;
 	}

}
 
int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
    double start_f = clock();

    cin >> g.s;
    //cerr << g.s << "\n";
    ll res = 0;
    g.init(g.s);
    manachar();
    int n = g.s.size();
    int rs = 0;
   // cerr << g.check(26, 27) << " " << g.s[25] << " " << g.s[26]<< "\n";
    for(int mid = 1;mid <= n;mid++){
    	int tp = d1[mid - 1] - 1;
    //	cerr << mid << " " << tp << "\n";
    	for(int l = mid - tp, r = mid + tp; l <= r;l++, r--){
    	//	cerr << "was " << " " << l << " " << r << "\n";
    		if(!g.is_were(l, r))
    			break;
    		rs++;
    	//	cerr << "was\n";
    	//	cerr << l << " " << r << " " << g.get_cnt(l, r) << "\n";
    		res = max(res, (r - l + 1ll) * g.get_cnt(l, r));
    	}
    }
    //cerr << g.get_cnt(5, 6) << "\n";
    for(int mid = 2;mid <= n;mid++){
    	if(g.s[mid - 1] != g.s[mid - 2])
    		continue;
    	int tp = d2[mid - 1];
    	for(int l = mid - tp, r = mid + tp - 1; l <= r;l++, r--){
    		if(!g.is_were(l, r))
    			break;
    		rs++;
    	//	cerr << l << " " << r << " " << g.get_cnt(l, r) << "\n";
    		res = max(res, (r - l + 1ll) * g.get_cnt(l, r));
    	}
    }
    //cerr << rs;
    cout << res;

   // cerr << (clock() - start_f) / CLOCKS_PER_SEC;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:244:12: warning: unused variable 'start_f' [-Wunused-variable]
     double start_f = clock();
            ^~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 0 / 27