oj.uz

답안 #616973

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
616973 2022-08-01T07:59:52 Z sentheta Palinilap (COI16_palinilap) C++17
0 / 100
 210 ms 14480 KB 
#include<algorithm>
#include<iostream>
#include<cassert>
#include<vector>
#include<string>
#include<array>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;

#define V vector
#define Int long long
#define rep(i,a,b) for(Int i=(Int)(a); i<(Int)(b); i++)
#define all(x) (x).begin(), (x).end()
#define nl '\n'
#define dbg(x) cout << "?" << #x << " : " << x << endl;
#define int long long
#define pii pair<int,int>

const int N = 1e5+5;

const int MOD = 1e9+7;
int SEED, SINV[N];
int bpow(int a,int b){
	int ret = 1;
	while(b){
		if(b&1) ret = ret*a%MOD;
		a = a*a%MOD; b /= 2;
	}
	return ret;
}
int inv(int a){
	return bpow(a, MOD-2);
}

int n;
string s;

// hash of ori string and reversed string
int h[N], rh[N];
int qry(int l,int r){
	int ret = h[r];
	if(l) ret -= h[l-1];
	(ret *= SINV[l] )%=MOD;
	if(ret<0) ret+=MOD;
	return ret;
}
int rqry(int l,int r){
	int ret = rh[l];
	if(r+1<n) ret -= rh[r+1];
	(ret *= SINV[n-1-r] )%=MOD;
	if(ret<0) ret+=MOD;
	return ret;
}


// add arithmetic sequence to range
// point query
int invmoe[N];
#define mid ((tl+tr)/2)
#define lc (v+1)
#define rc (v+2*(mid-tl+1))
struct Segtree{
	int st[2*N];
	int lzl[2*N], lzr[2*N];
	void upd(int l,int r,int addl,int addr,int v=0,int tl=0,int tr=n-1){
		if(r<tl || tr<l) return;
		if(l<=tl && tr<=r){
			int a = addl, b = addr*invmoe[r-l]%MOD;
			(addl = a + (tl-l)*b )%=MOD;
			(addr = a + (tr-l)*b )%=MOD;

			st[v] += addl;
			lzl[v] += addl; lzr[v] += addr;
			return;
		}
		if(lzl[v] || lzr[v]){
			upd(tl,tr,lzl[v],lzr[v], lc,tl,mid);
			upd(tl,tr,lzl[v],lzr[v], rc,mid+1,tr);
			lzl[v] = lzr[v] = 0;
		}
		upd(l,r,addl,addr, lc,tl,mid);
		upd(l,r,addl,addr, rc,mid+1,tr);
	}
	int qry(int i,int v=0,int tl=0,int tr=n-1){
		if(tl==tr) return st[v];
		if(lzl[v] || lzr[v]){
			upd(tl,tr,lzl[v],lzr[v], lc,tl,mid);
			upd(tl,tr,lzl[v],lzr[v], rc,mid+1,tr);
			lzl[v] = lzr[v] = 0;
		}
		if(i<=mid) return qry(i, lc,tl,mid);
		else return qry(i, rc,mid+1,tr);
	}
} segtree;
int loss[N];

// find longest [tl..l] == rev([r..tr]);
int f(int l,int r){
	int len = 0;
	for(int J=1<<20; J; J/=2)
		if(len+J<=n && l-len-J+1>=0 && r+len+J-1<n &&
			rqry(l-len-J+1,l)==qry(r,r+len+J-1)) len+=J;
	return len;
}

signed main(){
	rep(i,0,N){
		invmoe[i] = inv(i);
	}
	srand(time(0));
	//SEED = rand()%MOD;
	SEED = 3;
	SINV[0] = 1; SINV[1] = inv(SEED);
	rep(i,2,N){
		(SINV[i] = SINV[i-1]*SINV[1] )%=MOD;
	}
	assert(SEED*SINV[1]%MOD==1);

	cin >> s;
	n = s.size();


	int mul = 1;
	rep(i,0,n){
		if(i) h[i] = h[i-1];
		(h[i] += mul*s[i] )%=MOD;
		(mul *= SEED )%=MOD;
	}
	mul = 1;
	for(int i=n-1; i>=0; i--){
		if(i+1<n) rh[i] = rh[i+1];
		(rh[i] += mul*s[i] )%=MOD;
		(mul *= SEED )%=MOD;
	}

	// dbg(qry(1,1)); dbg(rqry(1,1));
	// return 0;

	// initial form
	int ans = 0;

	// segtree.qry(idx) = loss
	// mp[{idx,char}] = profit
	map<pii,int> mp;

	// even length palindrome
	rep(i,1,n){
		// [l..i-1] == rev([i..r])
		int len = f(i-1,i);
		int l = i-len, r = i+len-1;

		// dbg(i); dbg(len);
		// dbg(l); dbg(r);

		ans += len;
		if(l<=i-1) segtree.upd(l,i-1, 1,len);
		if(i<=r) segtree.upd(i,r, len,1);

		// if char were changed
		if(0<=l-1 && r+1<n){
			int tlen = f(l-2,r+2)+1;
			// dbg(tlen);
			mp[{l-1,s[r+1]}] += tlen;
			mp[{r+1,s[l-1]}] += tlen;
		}
		// cout << nl;
	}
	// cout << "##########" << nl;


	// odd length palindrome
	rep(i,0,n){
		// [l..i] == rev([i..r])
		int len = f(i,i);
		int l = i-len+1, r = i+len-1;

		// dbg(i); dbg(len);

		ans += len;
		segtree.upd(i,i, len-1,len-1);
		if(l<=i-1) segtree.upd(l,i-1, 1,len-1);
		if(i+1<r) segtree.upd(i+1,r, len-1,1);

		// if char were changed
		if(0<=l-1 && r+1<n){
			int tlen = f(l-2,r+2)+1;
			// dbg(tlen);
			mp[{l-1,s[r+1]}] += tlen;
			mp[{r+1,s[l-1]}] += tlen;
		}
	}

	// rep(i,0,n){
	// 	dbg(segtree.qry(i,i));
	// }





	// get answer
	int maxdelta = 0;
	for(auto[pr,cnt] : mp){
		auto[i,c] = pr;

		int delta = cnt - segtree.qry(i);
		maxdelta = max(maxdelta, delta);
	}
	ans += maxdelta;

	cout << ans << nl;

}

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 1876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 2520 KB Output is correct
2 Incorrect 25 ms 2532 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 210 ms 14480 KB Output isn't correct
2 Halted 0 ms 0 KB -