oj.uz

Submission #970625

# Submission time Handle Problem Language Result Execution time Memory
970625 2024-04-26T21:03:11 Z jcelin Palinilap (COI16_palinilap) C++14
100 / 100
 588 ms 29376 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;

#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()

const int mod = 998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 17;
const int MAXN = 1e5 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int base = 31;


string s;
int pw[MAXN], n;
ll ans, delt[MAXN][26];

//1 2 3 ... k
struct tournament{
	ll p[trsz], seg[trsz];
	int ad;
	
	void prop(int x, int lo, int hi){
		if(p[x] == 0) return;
		ll num = (hi - lo);
		seg[x] += p[x] * num;
		seg[x] += num * (num - 1) / (ll)2;
		if(x < off){
			int mid = (lo + hi) / 2;
			p[x * 2] += p[x];
			p[x] += (mid - lo);
			p[x * 2 + 1] += p[x];
		}
		p[x] = 0;
	}
	
	void update(int x, int lo, int hi, int a, int b){
		prop(x, lo, hi);
		if(lo >= b or hi <= a) return;
		if(lo >= a and hi <= b){
			p[x] = ad;
			ad += (hi - lo);
			prop(x, lo, hi);
			return;
		}
		int mid = (lo + hi) / 2;
		update(x * 2, lo, mid, a, b);
		update(x * 2 + 1, mid, hi, a, b);
		seg[x] = seg[x * 2] + seg[x * 2 + 1];
	}
	
	
	void upd(int l, int r){
		if(l >= r) return;
		ad = 1;
		update(1, 0, off, l, r);
	}
	
	ll query(int x, int lo, int hi, int a, int b){
		prop(x, lo, hi);
		if(lo >= b or hi <= a) return 0;
		if(lo >= a and hi <= b) return seg[x];
		int mid = (lo + hi) / 2;
		return query(x * 2, lo, mid, a, b) + query(x * 2 + 1, mid, hi, a, b);
	}
}t1;


//k k-1 k-2 .. 1
struct tournament2{
	ll p[trsz], seg[trsz];
	int ad;
	
	void prop(int x, int lo, int hi){
		if(p[x] == 0) return;
		ll num = (hi - lo);
		seg[x] += p[x] * num;
		seg[x] += num * (num - 1) / (ll)2;
		if(x < off){
			int mid = (lo + hi) / 2;
			p[x * 2 + 1] += p[x];
			p[x] += (mid - lo);
			p[x * 2] += p[x];
		}
		p[x] = 0;
	}
	
	void update(int x, int lo, int hi, int a, int b){
		prop(x, lo, hi);
		if(lo >= b or hi <= a) return;
		if(lo >= a and hi <= b){
			p[x] = ad;
			ad += (hi - lo);
			prop(x, lo, hi);
			return;
		}
		int mid = (lo + hi) / 2;
		update(x * 2 + 1, mid, hi, a, b);
		update(x * 2, lo, mid, a, b);
		seg[x] = seg[x * 2] + seg[x * 2 + 1];
	}
	
	
	void upd(int l, int r){
		if(l >= r) return;
		ad = 1;
		update(1, 0, off, l, r);
	}
	
	ll query(int x, int lo, int hi, int a, int b){
		prop(x, lo, hi);
		if(lo >= b or hi <= a) return 0;
		if(lo >= a and hi <= b) return seg[x];
		int mid = (lo + hi) / 2;
		return query(x * 2, lo, mid, a, b) + query(x * 2 + 1, mid, hi, a, b);
	}
}t2;

int add(int a, int b){
	a += b;
	if(a >= mod) a -= mod;
	return a;
}

int sub(int a, int b){
	a -= b;
	if(a < 0) a += mod;
	return a;
}

int mul(ll a, ll b){
	return (a * b) % mod;
}

struct hash{
	vi pf;
	void init(string ss){
		pf.clear();
		pf.PB(0);
		for(int i=1; i<=(int)ss.size(); i++) pf.PB(add(pf.back(), mul(pw[i], ss[i - 1] - 'a')));
	}
	
	int gval(int l, int r){
		return mul(pw[MAXN - 1 - l], sub(pf[r], pf[l - 1]));
	}
}h1, h2;

int vl(int l, int r, bool rev){
	if(rev){
		swap(l, r);
		l = n + 1 - l;
		r = n + 1 - r;
		return h2.gval(l, r);
	}
	
	return h1.gval(l, r);
}


int palin(int l, int r){
	return vl(l, r, 0) == vl(l, r, 1);	
}

void neparni(){
	for(int i=1; i<=n; i++){
		int lo = 1, hi = n, ret = 0;
		while(lo <= hi){
			int mid = (lo + hi) / 2;
			if(i - mid < 1 or i + mid > n){
				hi = mid - 1;
				continue;
			}
			
			if(palin(i - mid, i + mid)) lo = mid + 1, ret = mid;
			else hi = mid - 1;
		}
		
		ans += ret + 1;
		int l1 = i - ret - 1, r1 = i + ret + 1;
		t1.upd(l1 + 1, i);
		t2.upd(i + 1, r1);
		
		if(l1 == 0 or r1 == n + 1) continue;
		
		lo = 1, hi = n, ret = 0;
		while(lo <= hi){
			int mid = (lo + hi) / 2;
			if(l1 - mid < 1 or r1 + mid > n){
				hi = mid - 1;
				continue;
			}
			if(vl(l1 - mid, l1 - 1, 0) == vl(r1 + 1, r1 + mid, 1)) lo = mid + 1, ret = mid;
			else hi = mid - 1;
		}
		
		delt[l1][s[r1 - 1] - 'a'] += ret + 1;
		delt[r1][s[l1 - 1] - 'a'] += ret + 1;	
	}
}

void parni(){
	for(int i=1; i<n; i++){
		int l1, r1, lo, hi, ret;
		if(s[i - 1] != s[i]){
			l1 = i;
			r1 = i + 1;
		}else{
			lo = 1, hi = n, ret = 0;
			while(lo <= hi){
				int mid = (lo + hi) / 2;
				if(i - mid < 1 or i + 1 + mid > n){
					hi = mid - 1;
					continue;
				}
				
				if(palin(i - mid, i + 1 + mid)) lo = mid + 1, ret = mid;
				else hi = mid - 1;
			}
			
			ans += ret + 1;
			l1 = i - ret - 1, r1 = i + 1 + ret + 1;
			t1.upd(l1 + 1, i + 1);
			t2.upd(i + 1, r1);
		}
		if(l1 == 0 or r1 == n + 1) continue;
		
		
		lo = 1, hi = n, ret = 0;
		while(lo <= hi){
			int mid = (lo + hi) / 2;
			if(l1 - mid < 1 or r1 + mid > n){
				hi = mid - 1;
				continue;
			}
			if(vl(l1 - mid, l1 - 1, 0) == vl(r1 + 1, r1 + mid, 1)) lo = mid + 1, ret = mid;
			else hi = mid - 1;
		}
		
		delt[l1][s[r1 - 1] - 'a'] += ret + 1;
		delt[r1][s[l1 - 1] - 'a'] += ret + 1;
	}
}

void solve(){
	pw[0] = 1;
	for(int i=1; i<MAXN; i++) pw[i] = mul(pw[i - 1], base);
	cin >> s;
	n = s.size();
	
	h1.init(s);
	reverse(all(s));
	h2.init(s);
	reverse(all(s));
	
	neparni();
	parni();

	ll cans = ans;
	for(int i=1; i<=n; i++){
		for(int let=0; let<26; let++){
			if(s[i - 1] - 'a' == let) continue;
			cans = max(cans, delt[i][let] - t1.query(1, 0, off, i, i + 1) - t2.query(1, 0, off, i, i + 1) + ans);
		}
	}
	cout << cans << "\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while(tt--) solve();
	return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Correct 2 ms 4696 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 2 ms 4620 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7004 KB Output is correct
2 Correct 26 ms 7004 KB Output is correct
3 Correct 23 ms 7004 KB Output is correct
4 Correct 14 ms 6940 KB Output is correct
5 Correct 20 ms 7004 KB Output is correct
6 Correct 28 ms 7120 KB Output is correct
7 Correct 22 ms 7004 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 29016 KB Output is correct
2 Correct 551 ms 29280 KB Output is correct
3 Correct 527 ms 29244 KB Output is correct
4 Correct 446 ms 29016 KB Output is correct
5 Correct 455 ms 29224 KB Output is correct
6 Correct 459 ms 29268 KB Output is correct
7 Correct 450 ms 29168 KB Output is correct
8 Correct 524 ms 11048 KB Output is correct
9 Correct 453 ms 29092 KB Output is correct
10 Correct 456 ms 29124 KB Output is correct
11 Correct 532 ms 29276 KB Output is correct
12 Correct 519 ms 29220 KB Output is correct
13 Correct 510 ms 29376 KB Output is correct
14 Correct 452 ms 29276 KB Output is correct
15 Correct 451 ms 29248 KB Output is correct
16 Correct 588 ms 29244 KB Output is correct
17 Correct 420 ms 28228 KB Output is correct
18 Correct 448 ms 29136 KB Output is correct
19 Correct 436 ms 28692 KB Output is correct