Submission #259057

#	Time	Username	Problem	Language	Result	Execution time	Memory
259057		pure_mem	Palindromes (APIO14_palindrome)	C++14	73 / 100	1076 ms	64112 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;
 
	set< pair< pair< int, int >, int > > 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;
			}
			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;
			}
			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;
		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;
		ll hash3 = ((hs3[r] - hs3[l - 1] + mod3) % mod3) * pr3[(int)s.size() - l] % mod3;
		if(were.count(MP(MP(hash1, hash2), hash3)))
			return 0;
		were.insert(MP(MP(hash1, hash2), hash3));
		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, tp = tm - idx + 1;
			}
			else{
				tr = tm - 1;
			}
		}
	//	cerr << res << " " << tp << "\n";
		return res + tp - 1;
	}
}g;
 
int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
    cin >> g.s;
    //cerr << g.s << "\n";
    ll res = 0;
    g.init(g.s);
    int n = g.s.size();
   // cerr << g.check(26, 27) << " " << g.s[25] << " " << g.s[26]<< "\n";
    for(int mid = 1;mid <= n;mid++){
    	int tr = min(mid - 1, n - mid), tl = 1, tp = 0;
    	while(tl <= tr){
    		int tm = (tl + tr) / 2;
    		if(g.check(mid - tm, mid + tm))
    			tl = tm + 1, tp = tm;
    		else
    			tr = tm - 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;
    		//break; // UBRAT ------------------------------------------------
    	//	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 tr = min(mid - 2, n - mid), tl = 1, tp = 0;
    	while(tl <= tr){
    		int tm = (tl + tr) / 2;
    		if(g.check(mid - 1 - tm, mid + tm))
    			tl = tm + 1, tp = tm;
    		else
    			tr = tm - 1;
    	}
    	for(int l = mid - 1 - tp, r = mid + tp; l <= r;l++, r--){
    		if(!g.is_were(l, r))
    			break;
    	//	cerr << l << " " << r << " " << g.get_cnt(l, r) << "\n";
    		res = max(res, (r - l + 1ll) * g.get_cnt(l, r));
    	}
    }
    cout << res;
}

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