Ricarica (Timeout)

Buongiorno, gli ultimi tre casi di “Ricarica” mi vanno in timeout,mi potreste dare una mano a velocizzare il programma, vi lascio il codice di seguito grazie in anticipo:

#include <bits/stdc++.h>
using namespace std;
int main(){
   ofstream out("output.txt");
   ifstream in("input.txt");
   long long int N,M;
   in>>N>>M;
   typedef pair<long long int,long long int>coppia;
   vector<coppia>v(N);
   for(long long int i=0;i<N;i++){
   	in>>v[i].first;
   	in>>v[i].second;
   }
   long long int ris;
   bool A=false;
   for(int i=1;i<=M && A==false;i++){
   	long long int cont=i,x=1;
   	long long int j=0;
   	//cout<<i<<" "<<cont<<endl;
   	while(x<=M && cont!=0){
   		if(j<N){
   			if(x!=v[j].first){
   				x++;
   				cont--;
   			}
   			else{
   				cont+=v[j].second-v[j].first+1;
   				x=v[j].second+1;
   				j++;
   			}
   		}
   		else{
   			cont-=M-v[v.size()-1].second;
   			x=M+1;
   		}
   		//cout<<cont<<" "<<x<<endl;
   	}
   	if(cont>0){
   		ris=i;
   		A=true;
   	}
   }
   out<<ris;
}

Non mi è chiara la logica del programma comunque prova con questo input:

1 1000000000
100000 200000

Pensa che M può anche valere … mentre N 100000.
Prendi in considerazione l’idea di fare un ciclo di scansione non basato su M ma su N

Ho capito la tua idea e ho provato a fare una soluzione ma va ancora in timeout:

#include <bits/stdc++.h>
using namespace std;
int main(){
   ofstream out("output.txt");
   ifstream in("input.txt");
   long long int N,M;
   in>>N>>M;
   typedef pair<long long int,long long int>coppia;
   vector<coppia>v(N);
   for(long long int i=0;i<N;i++){
   	in>>v[i].first;
   	in>>v[i].second;
   	/*long long int n1,n2;
   	cin>>n1>>n2;
   	v.push_back(make_pair(n1,n2));*/
   }
   long long int ris;
   bool A=false;
   long long int j=1;
   while(A==false){
   	long long int i=0;
   	bool B=true;
   	long long int cont=j,x=0;
   	while(i<=N && B==true && x<=M){
   		if(i<N){
   			cont-=(v[i].first-1)-x;
   			x=v[i].first;
   			if(cont<=0){
   				B=false;
   			}
   			else{
   				cont+=v[i].second-v[i].first+1;
   				x=v[i].second;
   				i++;
   			}
   		}
   		else{
   			cont-=M-v[v.size()-1].second;
   			x=M+1;
   		}
   	}
   	if(cont<=0){
   		B=false;
   	}
   	if(B==true){
   		ris=j;
   		A=true;
   	}
   	else{
   		j++;
   	}
   }
   out<<ris;
}

Ripeto che non mi è chiaro l’algoritmo e quindi più di tanto non posso dire ma vedo un while dentro un while mentre c’è sicuramente una soluzione O(N). Hai a che fare con una spezzata triangolare che sale di k quando si attraversa un intervallo j di copertura lungo k e scende di k1 quando si attraversa un intervallo scoperto lungo k1 più le eventuali parti scoperte iniziali e finali.

Grazie mille ho capito come prendere 100 ti vorrei chiedere una cosa ma solo per curiosità, ma come fai a risolvere i problemi con cosi poco tempo,mi spiego meglio in parecchi problemi vedo sempre che tra i più veloci ci sei tu vorrei sapere se usi qualche tecnica particolare perchè mi piacerebbe impararla

Purtroppo non dispongo di soluzioni particolari ma di molto tempo da dedicare a questa attività che tra l’altro mi piace parecchio, inoltre non devo prepararmi per fare competizioni. Tutto questo significa che una volta trovata una soluzione posso dedicare anche molto tempo a migliorarla, cosa che il più delle volte avviene. Infine, fra i trucchi del mestiere, esistono funzioni per velocizzare i tempi di I/O che spesso e volentieri costituiscono una porzione cospicua del tempo che viene valutato per stabilire la velocità della soluzione.

Ho capito, avresti qualche consiglio da darmi per poter migliorare e allenarmi o impare cose nuove che possano essermi utili.

Direi che l’utilizzo di questo portale per allenamenti, cioè quello che stai già facendo, va benissimo. Comincia da quelli più facili e vai avanti, usa il forum etc. se poi arrivi ad un livello tale da voler puntare più in alto vedi Come qualificarsi per le IOI? per qualche consiglio aggiuntivo.

Grazie mille per i tuoi consigli