oj.uz

Submission #99239

# Submission time Handle Problem Language Result Execution time Memory
99239 2019-03-01T20:11:58 Z dsg213 Palinilap (COI16_palinilap) C++14
54 / 100
 109 ms 32108 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define ll long long
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
const int mod=1000000007,mxn=1000010;
string s;
int n;
ull p=313;
ull hap[mxn];
ull hal[mxn];
ull pot[mxn];
ull gethp(int left,int right){
	return hap[right]-hap[left-1]*pot[right-left+1];
}
ull gethl(int left,int right){
	return hal[left]-hal[right+1]*pot[right-left+1];
}
ll acc[mxn];
ll ilz[mxn];
ll wie[mxn][26];
ll ans;
void liczsro(int x){
	int mn=1;
	int mx=min(x,n-x+1);
	////cout <<mx <<" ";
	while(mn<mx){
		int sr=(mn+mx+1)/2;
		if(gethp(x-sr+1,x)==gethl(x,x+sr-1)){
			mn=sr;
		}
		else{
			mx=sr-1;
		}
	}
	////cout <<mn <<" ";
	acc[x-mn]+=1;
	acc[x]-=2;
	acc[x+mn]+=1;
	ilz[x]-=mn;
	int baz=mn;
	ans+=baz;
	if(baz==min(x,n-x+1)){
		////cout <<"0\n";
		return;
	}
	mx=min(x,n-x+1);
	mn=baz+1;
	while(mn<mx){
		int sr=(mn+mx+1)/2;
		if(gethp(x-sr+1,x-baz-1) == gethl(x+baz+1,x+sr-1)){
			mn=sr;
		}
		else{
			mx=sr-1;
		}
	}
	int dod=mn-baz;
	////cout <<baz <<" "<<dod <<"\n";
	char c1=s[x-baz-1]-'a';
	char c2=s[x+baz-1]-'a';
	wie[x-baz][c2]+=dod;
	wie[x+baz][c1]+=dod;
	////cout <<x  <<" " <<baz <<" " <<c2+'a' <<"\n";
}
void liczd(int x){
	int mn=0;
	int mx=min(x,n-x);
	while(mn<mx){
		int sr=(mn+mx+1)/2;
		if(gethp(x-sr+1,x)==gethl(x+1,x+sr)){
			mn=sr;
		}
		else{
			mx=sr-1;
		}
	}
	////cout <<mn <<" ";
	acc[x-mn]+=1;
	acc[x]-=1;
	acc[x+1]-=1;
	acc[x+mn+1]+=1;
	//ilz[x]-=mn;
	int baz=mn;
	ans+=baz;
	if(baz==min(x,n-x)){
		////cout <<"0 ";
		return;
	}
	mx=min(x,n-x);
	mn=baz+1;
	////cout <<mx <<" ";
	while(mn<mx){
		int sr=(mn+mx+1)/2;
		if(gethp(x-sr+1,x-baz-1) == gethl(x+baz+2,x+sr)){
			mn=sr;
		}
		else{
			mx=sr-1;
		}
	}
	int dod=mn-baz;
	////cout <<dod <<" ";
	char c1=s[x-baz-1]-'a';
	char c2=s[x+baz]-'a';
	wie[x-baz][c2]+=dod;
	wie[x+baz+1][c1]+=dod;
	////cout <<x-baz <<" " <<'a'+c2 <<"\n";
}
void pro(){
	ll pr=0;
	ll val=0;
	for(int i=0;i<=n;i++){
		ilz[i]+=val;
		pr+=acc[i];
		val+=pr;
	}
}
int main(){
	cin >>s;
	n=s.size();
	pot[0]=1;
	for(ull i=1;i<=mxn-10;i++){
		pot[i]=pot[i-1]*p;
	}
	for(int i=0;i<n;i++){
		hap[i+1]=hap[i]*p+s[i];
	}
	for(int i=n;i>0;i--){
		hal[i]=hal[i+1]*p+s[i-1];
	}
	/*while(1){
		int a,b;
		cin >>a >>b;
		//cout <<gethp(a,b) <<"\n";
		//cout <<gethl(a,b) <<"\n";
	}*/
	for(int i=1;i<=n;i++){
		liczsro(i);
	}
	////cout <<"\n";
	for(int i=1;i<n;i++){
		liczd(i);
	}
	////cout <<"\n";
	pro();
	////cout <<"\n";
	/*for(int i=0;i<=n;i++){
		//cout <<acc[i] <<" ";
	}
	//cout <<"\n";
	*/
	/*for(int i=0;i<=n;i++){
		//cout <<ilz[i] <<" ";
	}*/
	//cout <<ans<<"\n";
	ll wyn=ans;
	for(int i=1;i<=n;i++){
		//cout <<ilz[i] <<" "; 
		for(int j=0;j<26;j++){
			wyn=max(wyn,ans+wie[i][j]-ilz[i]);
		}
	}
	//cout <<"\n";
	for(int i=1;i<=n;i++){
		ll x=0;
		for(int j=0;j<26;j++){
			x=max(x,wie[i][j]);
		}
		//cout <<x<<" ";
	}
	//cout <<"\n";
	cout <<wyn;
}

Compilation message

palinilap.cpp: In function 'void liczsro(int)':
palinilap.cpp:68:15: warning: array subscript has type 'char' [-Wchar-subscripts]
  wie[x-baz][c2]+=dod;
               ^
palinilap.cpp:69:15: warning: array subscript has type 'char' [-Wchar-subscripts]
  wie[x+baz][c1]+=dod;
               ^
palinilap.cpp: In function 'void liczd(int)':
palinilap.cpp:112:15: warning: array subscript has type 'char' [-Wchar-subscripts]
  wie[x-baz][c2]+=dod;
               ^
palinilap.cpp:113:17: warning: array subscript has type 'char' [-Wchar-subscripts]
  wie[x+baz+1][c1]+=dod;
                 ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8192 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Correct 9 ms 8192 KB Output is correct
4 Correct 9 ms 8188 KB Output is correct
5 Correct 9 ms 8192 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9344 KB Output is correct
2 Correct 11 ms 9344 KB Output is correct
3 Correct 11 ms 9344 KB Output is correct
4 Correct 10 ms 8832 KB Output is correct
5 Correct 11 ms 9216 KB Output is correct
6 Correct 13 ms 9344 KB Output is correct
7 Correct 12 ms 9344 KB Output is correct

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 31992 KB Output is correct
2 Correct 66 ms 31992 KB Output is correct
3 Correct 57 ms 31992 KB Output is correct
4 Correct 88 ms 32108 KB Output is correct
5 Correct 81 ms 31996 KB Output is correct
6 Correct 106 ms 31992 KB Output is correct
7 Correct 80 ms 31944 KB Output is correct
8 Correct 36 ms 11640 KB Output is correct
9 Correct 94 ms 31992 KB Output is correct
10 Correct 78 ms 31992 KB Output is correct
11 Correct 75 ms 32032 KB Output is correct
12 Correct 87 ms 32056 KB Output is correct
13 Correct 109 ms 31992 KB Output is correct
14 Correct 76 ms 32024 KB Output is correct
15 Correct 90 ms 31992 KB Output is correct
16 Correct 81 ms 31908 KB Output is correct
17 Correct 66 ms 31992 KB Output is correct
18 Incorrect 74 ms 31992 KB Output isn't correct
19 Halted 0 ms 0 KB -