Stavo risolvendo “numeri” e sono arrivato ad una soluzione 100/100 che però non usa la ricerca binaria,
fa questo:
scorre l’array con le piante tenendo la somma, sottraendo da sinistra e aggiungendo da destra
Quindi quale sarebbe la soluzione che usa la ricerca binaria?
O forse il tag è errato?
Il tag ricerca binaria l’ho messo io, quindi ti posso spiegare la mia soluzione che però è meno efficiente della tua:
Creo un vector V che contiene all’indice i la somma del valore delle prime i piante. Esiste una sequenza valida che termina con l’i-esima pianta solo se esiste un valore j<i tale che V[i]-V[j]=M. Dato che le piante hanno solo valori non negativi allora il vector V è ordinato, quindi posso usare la ricerca binaria per trovare j valido, se esiste.
Ah capito, grazie della spiegazione 
Anch’io avevo pensato a questa soluzione, ma… la complessità nel caso peggiore non sarebbe NLog(N)? Se non sbaglio con N= 10^6 va fuori tempo.
Una soluzione in \mathcal O(N\log N) dovrebbe funzionare, tuttavia per input di queste dimensioni solitamente si usa fast I/O.
Un algoritmo in \mathcal O(NlogN) con N \leq 10^6 può entrare comunque nei limiti di tempo se ha costanti piccole, come è il caso nella ricerca binaria. Se l’algoritmo utilizzasse strutture dati più complesse molto probabilmente andrebbe fuori tempo anche con la stessa complessità asintotica.
In questo caso poi le operazioni sono leggermente di meno di \mathcal O(NlogN), \sum_{i=1}^{N}{log_2(i)} \approx 1,85\cdot10^7, che si riesce a far andare in un tempo decente, magari usando il fastin.
Nei problemi più recenti spesso quando si vuole una soluzione lineare si mette N \approx 10^7, dove solo Chen riesce a nascondere fattori logaritmici.
Cosa vorrebbe dire?per nascondere intendi evitarli?
Intendo ottimizzare, forte.
Se non sbaglio alle ultime nazionali ha risolto lungomare in \mathcal O(NlogN) con N \leq 10^7, col piccolo dettaglio che la binaria che faceva non era in log_2N ma in log_{22}N, riuscendo a farla stare nei tempi.
Io neanche dopo un sacrificio a Tarjan e una seduta spiritica con Turing riesco a fare queste cose.
Come ha fatto a fare la ricerca binaria in \log_{22}N?
Sono troppo curioso 
Magia nera. Pura magia nera.
Mi pare prendesse il pivot non a metà dell’intervallo ma a un ventiduesimo, come complessità non è veramente log_{22}N ma per quel problema velocizzava la soluzione.
Ho provato a scrivere una soluzione in O(Nlog(N)) ma totalizzo solamente 55/100. In 4 casi va fuori tempo di al massimo 0.160, e in 5 casi sbaglia l’output (può darsi che vada in overflow?)
Hai provato con il fast I/O?
Per i casi sbagliati dubito che sia overflow, se leggi bene la assunzioni noterai che la soluzione è inferiore a 2^{31}.
Puoi postare il codice?
ecco la soluzione che totalizza 55/100:
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef long long ll;
ll tot = 0;
int somma, n;
unordered_map <ll, bool> mappa;
vector <pair <ll, int> > v;
int readInt()
{
int res = 0;
char ch = 0;
while(ch < ‘0’) ch = getchar_unlocked();
for(; ch >= ‘0’; ch = getchar_unlocked()) res = res * 10 + ch - ‘0’;
return res;
}
int cerca(ll numero){
int lb = -1,
ub = v.size();
while(lb+1 < ub)
{
int m = (lb+ub)/2;
if(v[m].first == numero)
return m;
else if(v[m].first > numero)
ub = m;
else
lb = m;
}
return ub;
}
int main(){
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
somma = readInt();
n = readInt();
v.push_back(mp(0, 1)); mappa[0] = true;
for(int i=0; i<n; i++)
{
int a;
a = readInt();
int ultimo = v.size()-1; int New = v[ultimo].first+a;
mappa[New]=true;
if(a!=0)
v.push_back(mp(New, 1));
else
v[ultimo].second++;
}
if(v.size() == 1) // tutti zero
{
cout << n*(n+1)/2;
return 0;
}
for(int i=v.size()-1; i>=0; i--)
{
ll q= v[i].first-somma;
if(!mappa[q])
continue;
if(q < 0)
break;
tot += (v[i].second * v[cerca(q)].second);
}
cout << tot;
}
creo un vector di pair di somme prefisse in cui tengo la frequenza: v[i].first contiene la somma prefissa, mentre v[i].second contiene quante volte quel valore compare (che equivale al numero di zeri dopo quel numero); inoltre tengo in un unordered map i valori presente nel vector di somme prefisse. Poi faccio un ricerca binaria per trovare i numeri “complementari”.
Spero di essere stato chiaro.
P.S.: non riesco a postare il codice tutto intero: me lo spezza in due prima del main 
Ho provato a togliere la unordered_map e non va più fuori tempo. Ora però faccio 75/100 perchè mi sbaglia degli output (testacase 11, 12, 17, 18, 19) 
Per incollare il codice senza che lo tagli basta mettere tre accenti gravi all’inizio e alla fine:
//codice
Ho guardato il tuo codice, in particolare questa parte:
if(v.size() == 1) // tutti zero
{
cout << n*(n+1)/2;
return 0;
}
Oltre che inutile, mi sembra anche sbagliata, prova questo input:
0 2
5 5
Tuttavia non è questa la causa degli output sbagliati, la causa è l’overflow:
int New = v[ultimo].first+a;
sostituisci int con ll e otterrai 100/100.
in questo caso non entra neanche in questa if [quote=“Borto, post:17, topic:4315”]
if(v.size() == 1) // tutti zero
{
cout << n*(n+1)/2;
return 0;
}
[/quote]
perchè nel vector v all’inizio pusho sempre uno 0.
immaginavo, solo che non trovavo dove potesse essere.
Grazie mille dell’ aiuto!
P.S.: ho trovato anche una soluzione molto più veloce (direi con una complessità lineare).
Chiedo venia, comunque il secondo d’esempio è piuttosto ingannante e complica solamente la soluzione, io non l’ho neanche considerato eppure la mia soluzione fa 100/100.
La soluzione lineare non è troppo difficile, io l’ho risolto così:
l’idea è quella di tenersi due indici i e j e calcolarsi la somma da V_i a V_j, se tale somma è inferiore a M, incremento j, se è maggiore di M, incremento i e infine se è uguale conto gli zeri all’inizio e alla fine e li moltiplico tra di loro incrementando il risultato.
Piccola curiosità, Quali sono i tempi della vostra soluzione?