# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
219227 | L01 | Vudu (COCI15_vudu) | C++17 | 420 ms | 20344 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <algorithm>
using namespace std;
int tnumeros,ABI[1000006],tdiferentes,limite;
long long int anterior,tsubsecuenncias;
struct casilla
{
long long int valor;
int pos;
};
casilla numeros[1000006];
bool ordpos(casilla a,casilla b)
{
return a.pos<b.pos;
}
bool ordval(casilla a,casilla b)
{
return a.valor<b.valor;
}
void actualiza(int pos)
{
while(pos<=tnumeros)
{
ABI[pos]++;
pos+=pos&-pos;
}
}
int suma(int pos)
{
int ret=0;
while(pos>0)
{
ret+=ABI[pos];
pos-=pos&-pos;
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>tnumeros;
for(int i=1;i<=tnumeros;i++)
{
cin>>numeros[i].valor;
numeros[i].pos=i;
}
cin>>limite;
for(int i=1;i<=tnumeros;i++)
{
numeros[i].valor+=numeros[i-1].valor-limite;
}
sort(numeros,numeros+1+tnumeros,ordval);
for(int i=0;i<=tnumeros;i++)
{
if(i==0 or numeros[i].valor!=anterior)
{
anterior=numeros[i].valor;
numeros[i].valor=++tdiferentes;
}
else
{
numeros[i].valor=tdiferentes;
}
}
sort(numeros,numeros+1+tnumeros,ordpos);
actualiza(numeros[0].valor);
for(int i=1;i<=tnumeros;i++)
{
tsubsecuenncias+=suma(numeros[i].valor);
actualiza(numeros[i].valor);
}
cout<<tsubsecuenncias;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |