Given $$$q \; (q \le 2 \cdot 10^5)$$$ operations:
- Insert a pair $$$(a,b)$$$.
- Given pair $$$(x,y)$$$, find the minimum value of $$$ax + by$$$.
$$$|a|,|b|,|x|,|y| \le 10^6$$$.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | cry | 158 |
4 | awoo | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | maroonrk | 152 |
Given $$$q \; (q \le 2 \cdot 10^5)$$$ operations:
$$$|a|,|b|,|x|,|y| \le 10^6$$$.
We call a string $$$s$$$ of length $$$n$$$ good, if and only if $$$n \bmod 2 = 0$$$ and $$$s[1,\dfrac{n}{2}] = s[\dfrac{n}{2}+1,n]$$$ (i.e. there exists a string $$$t$$$ that $$$s = t + t$$$.)
You are given a string $$$s$$$. For each $$$r \in [1,n]$$$:
Is the guess correct?
We call a $$$\texttt{01}$$$ string $$$s$$$ of length $$$n$$$ good, if and only if:
Given a $$$\texttt{01}$$$ string $$$s$$$, calculate how many substrings in $$$s$$$ are good.
$$$n \le 5 \times 10^5$$$.
We transform the condition $$$s_i \ne s_{n-i+1}$$$ into if we change all $$$\texttt{0} \to \texttt{1},\texttt{1} \to \texttt{0}$$$ and reverse it to get a string $$$t$$$, $$$s$$$ is good if and only if $$$s = t$$$. Then we can use suffix array or manachar to get the answer.
Then, the hash solution did the same transformation and use hashing to get the answer with $$$\text{base} = 10^9+7$$$ and $$$\text{mod} = 2^{64}-1$$$ (unsigned long long
). Can it be hacked? I have done stress test for $$$15000$$$ test cases :(
I will provide the hash code and the suffix array code below, if you need to make a stress test.
/**
* author: sunkuangzheng
* created: 24.01.2024 15:12:52
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 2e6+5;
using namespace std;
int T,n,m,sa[N],rk[N],ok[N],h[N],st[22][N];string s;
void los(){
cin >> n >> s,s = s + '#' + string(s.rbegin(),s.rend());
for(int i = n + 1;i < s.size();i ++) s[i] ^= 1;
auto SA = [&](string &s,int &n){
s = " " + s,n = s.size() - 1;
for(int i = 1;i <= n;i ++) sa[i] = i,rk[i] = s[i];
for(int j = 1;j < n;j *= 2){
for(int i = 1;i <= n;i ++) ok[i] = rk[i]; int p = 0;
sort(sa+1,sa+n+1,[&](int x,int y){return rk[x] < rk[y] || rk[x] == rk[y] && rk[x + j] < rk[y + j];});
auto cmp = [&](int x,int y){return ok[x] == ok[y] && ok[x + j] == ok[y + j];};
for(int i = 1;i <= n;i ++) if(cmp(sa[i],sa[i-1])) rk[sa[i]] = p; else rk[sa[i]] = ++p;
}for(int i = 1,k = 0;i <= n;h[rk[i ++]] = k) for(k --,k = max(k,0);s[i + k] == s[sa[rk[i] - 1] + k];k ++);
for(int i = 1;i <= n;i ++) st[0][i] = h[i];
for(int j = 1;j <= __lg(n);j ++) for(int i = 1;i + (1 << j) - 1 <= n;i ++)
st[j][i] = min(st[j-1][i],st[j-1][i + (1 << j - 1)]);
};SA(s,m);
auto lcp = [&](int i,int j){
if(i = rk[i],j = rk[j],i > j) swap(i,j); assert(i != j);
int k = __lg(j - i);
return min(st[k][i+1],st[k][j-(1<<k)+1]);
};auto get = [&](int i){return n + 2 + n - i;};
ll ans = 0;
for(int i = 1;i < n;i ++) ans += lcp(get(i),i + 1);
cout << ans;
}int main(){
ios::sync_with_stdio(0),cin.tie(0);
for(T = 1;T --;) los();
}
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N=5e5,base=1e9+7;
char s[N+10];
ull h1[N+10],h2[N+10],p[N+10];
bool t1[N+10],t2[N+10];
int n;
void init()
{
p[0]=1ull;
for(int i=1;i<=n;i++) p[i]=p[i-1]*base;
for(int i=1;i<=n;i++) h1[i]=h1[i-1]*base+(s[i]=='1');
for(int i=1;i<=n;i++) h2[i]=h2[i-1]*base+(s[n-i+1]=='0');
}
ull hs(ull *h,int l,int r) {return h[r]-h[l-1]*p[r-l+1];}
bool check(int l,int r) {return hs(h1,l,r)==hs(h2,n-r+1,n-l+1);}
int erfen(int i)
{
int l=0,r=min(i,n-i),ans=0;
while(l<=r)
{
int mid=(l+r)/2;
if(check(i-mid+1,i+mid))
{
l=mid+1;
ans=mid;
}
else r=mid-1;
}
return ans;
}
int main()
{
ll ans=0;
scanf("%d%s",&n,s+1);
init();
for(int i=1;i<n;i++) ans+=erfen(i);
printf("%lld",ans);
return 0;
}
Is there any extension which can change the submissions status such as changing Wrong answer on test X
to Wonderful answer on test X
? If it exists where can I find it?
Name |
---|