Sto provando a risolvere i subtask 4 e 5 di Hasta(quelli in cui R è crescente) e non capisco perché mi da WA.
Qualcuno riuscirebbe a dirmi dov’è l’errore? Grazie.
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
// Declaring functions
#define MAXN 200005
int n,k;
int *v;
int *r;
vector<vector<int> > prefix;
vector<int>st(4*MAXN,0);
vector<vector<int> >persone;
void update(int i,int l,int r,int q,int val)
{
if(l==r)
{
st[i]=val;
return;
}
int mid=(l+r)/2;
if(q<=mid)update(i*2+1,l,mid,q,val);
else update(i*2+2,mid+1,r,q,val);
st[i]=st[i*2+1]+st[i*2+2];
}
int get_sum(int i,int l,int r,int ql,int qr)
{
if(l>=ql&&r<=qr)return st[i];
if(l>qr||r<ql)return 0;
int mid=(l+r)/2;
return get_sum(i*2+1,l,mid,ql,qr)+get_sum(i*2+2,mid+1,r,ql,qr);
}
void inizia(int N,int K, int V[], int R[]){
n=N,k=K,v=V,r=R;
if(n<=2000||k<=100)
{
prefix.resize(N+1,vector<int>(k,0));
for(int i=0;i<N;i++)
{
for(int j=0;j<K;j++)
{
prefix[i+1][j]=prefix[i][j];
}
prefix[i+1][v[i]]++;
}
return;
}
persone.resize(K);
}
int last=-1;
int istiga(int left,int right)
{
if(n<=2000||k<=100)
{
int conta=0;
for(int i=0;i<k;i++)
{
if(prefix[right+1][i]-prefix[left][i]==r[i])conta+=r[i];
}
return conta;
}
while (last<right) {
last++;
int classe=v[last];
persone[classe].push_back(last);
int dim=persone[classe].size();
if(dim==r[classe])
{
update(0,0,n-1,persone[classe][0],r[classe]);
}
else if(dim==r[classe]+1)
{
update(0,0,n-1,persone[classe][dim-r[classe]],r[classe]);
update(0,0,n-1,persone[classe][0],-r[classe]);
}
else if(dim>r[classe]+1)
{
update(0,0,n-1,persone[classe][dim-r[classe]],r[classe]);
update(0,0,n-1,persone[classe][dim-r[classe]-1],-r[classe]);
update(0,0,n-1,persone[classe][dim-r[classe]-2],0);
}
}
return get_sum(0,0,n-1,left,right);
}