\(100+100+40+0\), T3 não otimizado corretamente resultou em \(20\) pontos perdidos.
Posteriormente, descobri que durante a competição, a solução para T3 tinha complexidade de tempo e correção corretas, apenas com uma grande contsante que me fez achar que não executaria dentro do tempo limite.
A. Conjunto
A resposta satisfaz a propriedade monótona, utilizando ponteiros duplos para contar a resposta e uma árvore de segmentos de valor para manter o maior segmento contínuo no domínio dos valores, com complexidade de tempo \(O(n\log n)\).
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=2e5+10;
int n,k,b[MAXN],contagem[MAXN];
long long resposta;
struct arvore{int esq,dir,compr;}t[MAXN<<2];
inline void modificar(int l,int r,int no,int x)
{
if(l==r){t[no].esq=t[no].dir=t[no].compr=(contagem[x])?1:0;return ;}
int mid=(l+r)>>1;
if(x<=mid) modificar(l,mid,no<<1,x);
else modificar(mid+1,r,no<<1|1,x);
t[no].esq=t[no<<1].esq+(t[no<<1].esq==(mid-l+1)?t[no<<1|1].esq:0);
t[no].dir=t[no<<1|1].dir+(t[no<<1|1].dir==(r-mid)?t[no<<1].dir:0);
t[no].compr=max(max(t[no<<1].compr,t[no<<1|1].compr),t[no<<1].dir+t[no<<1|1].esq);
return ;
}
int main()
{
freopen("conjunto.in","r",stdin);
freopen("conjunto.out","w",stdout);
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
cin>>n>>k;for(int i=1;i<=n;++i) cin>>b[i];
++contagem[b[1]];modificar(1,n,1,b[1]);
for(int l=1,r=2;l<=n;++l)
{
while(r<=n)
{
++contagem[b[r]];if(contagem[b[r]]==1) modificar(1,n,1,b[r]);
if(t[1].compr<=k){++r;continue;}
--contagem[b[r]];modificar(1,n,1,b[r]);break;
}
resposta+=(r-l);--contagem[b[l]];if(!contagem[b[l]]) modificar(1,n,1,b[l]);
}
cout<<resposta<<'\n';return 0;
}
B. Fila de Diferenças
Um número, se não for o máximo, nunca será o máximo no futuro. O máximo só será removido quando restar apenas um número.
Analisando separadamente, primeiro consideramos a expectativa de cada número removido. Mantemos o máximo atual \(maximo\) e a soma dos outros valores multiplicados por suas probabilidades de não serem removidos \(soma\), junto com a contagem desses outros valores \(contagem\).
pop:
- Nenhum número: o número inserido torna-se o \(maximo\).
- Pelo menos um número: \(x\) é comparado com \(maximo\), o maior torna-se \(maximo\), e o menor é inserido entre os outros valores.
push:
- \(contagem=0\): a expectativa é \(maximo\), e então \(maximo\) é removido.
- \(contagem>0\): a expectativa é \(soma\times\dfrac{1}{contagem}\), e atualizamos \(soma\gets soma\times(1-\dfrac{1}{contagem})\).
Agora, consideramos o tempo esperado até cada número ser removido.
Se um número é removido como máximo, seu tempo de remoção é fixo e conhecido. Portanto, focamos apenas no tempo esperado para números removidos dos "outros valores".
Seja \(c_i\) o valor de \(contagem\) durante uma operação push quando \(i\) é o tempo atual.
Para um número adicionado aos "outros valores" no tempo \(t\), seu tempo esperado de remoção é \(\sum\limits_{i\in[t,n],c_i>0}\dfrac{i}{c_i}\times \prod\limits_{j\in[t,i-1],c_j>0} (1-c_j)\).
Cada resposta corresponde a um sufixo. Portanto, processamos offline, de \(n\to 1\). Se for uma operação push com \(c_i>0\), atualizamos \(Resposta\gets \dfrac{i}{c_i}+(1-\dfrac{1}{c_i})\times Resposta\), e definimos \(resposta_j=Resposta\) para todos os números \(j\) adicionados aos "outros valores" no tempo \(t_j=i\).
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
using namespace std;
const int MAXN=1e6+10,MOD=998244353;
int n,tempo[MAXN],cont[MAXN];
long long inverso[MAXN],MAXIMO,maximo,soma,contagem,resposta[MAXN];
typedef pair<int,int> P;vector <P> v;
int main()
{
freopen("fila.in","r",stdin);
freopen("fila.out","w",stdout);
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
cin>>n;inverso[0]=inverso[1]=1;
for(int i=2;i<=n;++i) inverso[i]=(-inverso[MOD%i]*(MOD/i)%MOD+MOD)%MOD;
for(int i=1;i<=n;++i)
{
int op,x;cin>>op;
if(!op)
{
cin>>x;
if(!MAXIMO) MAXIMO=x,maximo=i;
else if(x>MAXIMO) soma+=MAXIMO,MAXIMO=x,tempo[maximo]=i,maximo=i,contagem+=1;
else soma+=x,tempo[i]=i,contagem+=1;soma%=MOD;
}
else
{
if(!contagem){resposta[i]=MAXIMO,resposta[maximo]=i,MAXIMO=0;}
else
{
resposta[i]=soma*inverso[contagem]%MOD,cont[i]=contagem;
soma=(soma+MOD-resposta[i])%MOD,contagem-=1;
}
}
}
for(int i=1;i<=n;++i) if(tempo[i]) v.push_back({tempo[i],i});
sort(v.begin(),v.end());long long RESPOSTA=0;
for(int i=n,cur=v.size()-1;i>=1;--i)
{
if(cont[i]) RESPOSTA=(RESPOSTA*(cont[i]-1)%MOD+i)%MOD*inverso[cont[i]]%MOD;
while(cur>=0&&v[cur].first==i)
resposta[v[cur].second]=RESPOSTA,--cur;
}
for(int i=1;i<=n;++i) cout<<resposta[i]<<' ';
cout<<'\n';return 0;
}
C. Bolo
Seja \(F(l,r,p)\) o custo mínimo para o intervalo \([l,r]\] considerando apenas as camadas \(p\) ou superiores. A resposta é \(F(1,n,0)\).
Seja \(min_{l,r}\) o índice do menor número em \([l,r]\], e \(max_{l,r}\) o índice do maior.
Para \(F(l,r,p)\), consideramos primeiro o custo mínimo de cortar todas as camadas \(p+1\sim a_{min_{l,r}}\) em todo o intervalo \([l,r]\]:
[F(l,min_{l,r}-1,a_{min_{l,r}}+1)+F(min_{l,r}+1,r,a_{min_{l,r}}+1)+\dfrac{(a_{max_{l,r}}-p+a_{max_{l,r}}-(a_{min_{l,r}}-1))\times (a_{min_{l,r}}-p)}{2} ]Outra abordagem é remover a coluna do valor máximo e cortá-la separadamente, com custo mínimo \(F(l,max_{l,r}-1,p)+F(max_{l,r}+1,r,p)+(a_{max_{l,r}}-p)\). Tomamos o mínimo entre essas duas abordagens.
A transição certamente ocorre entre esses dois casos. Pode-se intuir que o número de estados válidos é \(O(n^2)\).
Considerando como enumerar a divisão do bloco mais baixo do máximo no intervalo. Uma abordagem é escolher a coluna onde está o máximo; caso contrário, suponha que escolhemos o intervalo \(x,y\) e subtraímos seu valor mínimo. Pode-se observar que essa operação pode ser alterada para primeiro operar em \([l,r]\] e depois em \([x,y]\] sem alterar o custo, e os valores ao redor diminuem, portanto essa abordagem não é pior. Assim, a transição torna-se \(O(1)\).
O número real de estados válidos é \(O(n^2)\). Primeiro, observa-se que a condição necessária é \(l=1\vee a_{l-1}< k\vee a_{l-1}>\max_{i\in[l,r]}a_i\) e \(r=n\vee a_{r+1}< k\vee a_{r+1}>\max_{i\in[l,r]}a_i\). Especificamente, ao reduzir os limites, atualizamos \(k\) com o mínimo ou reduzimos com o máximo, então ambos os extremos do intervalo devem satisfazer essas condições. Em seguida, observa-se que para cada \(k\), o número de intervalos \([l,r]\] que satisfazem a condição é na verdade \(O(n)\). Na verdade, isso é equivalente a construir uma árvore de cartesiana com todos os segmentos máximos onde \(a_i>k\).
Uma tabela de hash implementada manualmente com memoização resolve o problema.
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 3010, MH = 10000141;
int n, a[MAXN], pre[MAXN], f[MAXN][MAXN], g[MAXN][MAXN], c;
int h[MH + 10];
struct E
{
long long v, w, t;
} e[6000050];
void A(long long x,int a)
{
e[++c] = {x, a, h[x % MH]};
h[x % MH] = c;
}
int Q(long long x)
{
for (int i = h[x % MH]; i; i = e[i].t)
if (e[i].v == x)
return e[i].w;
return -1;
}
inline int FAZER(int l, int r, int p)
{
if (l > r)
return 0;
if (l == r)
return a[l] - p;
if (Q(((1ll * l * MAXN + r) << 32) + p)!=-1)
return Q(((1ll * l * MAXN + r) << 32) + p);
int m = f[l][r], ans = 0, MAX = a[g[l][r]];
ans = ((MAX << 1) - p - a[m] + 1) * (a[m] - p) / 2 + FAZER(l, m - 1, a[m]) + FAZER(m + 1, r, a[m]);
ans = min(ans, FAZER(l, g[l][r] - 1, p) + FAZER(g[l][r] + 1, r, p) + (MAX - p));
return A(((1ll * l * MAXN + r) << 32) + p, ans), ans;
}
signed main()
{
freopen("bolo.in", "r", stdin);
freopen("bolo.out", "w", stdout);
cin.tie(0), cout.tie(0);
ios::sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i], pre[i] = pre[i - 1] + a[i];
for (int i = 1; i <= n; ++i)
{
f[i][i] = g[i][i] = i;
for (int j = i + 1; j <= n; ++j)
f[i][j] = (a[j] < a[f[i][j - 1]]) ? j : f[i][j - 1],
g[i][j] = (a[j] > a[g[i][j - 1]]) ? j : g[i][j - 1];
}
cout << FAZER(1, n, 0) << '\n';
return 0;
}
D. Substituição de Caracteres
Não resolvido.