126 Lungimi de interval

[•fogab]

Am nevoie si eu de lamurire 
Fac sortarea in NlogN pe un vector<pair<int,int>> si iau TLE
citire numai - 244 ms - http://infoarena.ro/job_detail/188199
citire + sortare numai - TLE - http://infoarena.ro/job_detail/188201
Daca nu intra nici cu vectoruri si cu citire din stream in timp, in pascal e chiar "impossible, like girls in stilettoes trying to run".
N-as dori sa renunt de STL si de programarea propriu-zis C++ 
Hint?

[•wefgef]

Probabil ca sunt o gramada de chestii unde ai putea optimiza: sa nu folosesti un vector ci un array static, poate poti sa optimizezi citirea, etc. E frumos C++, dar deocamdata e mai sigur in concursuri sa nu faci excese de STL.

[•fogab]

Cine se mai duce la concursuri 
Cel putin la ACM nu apar probleme cu limitele stranse de timp 
Merci oricum.. back to the basics 

PS : Pascal chiar are vreo sansa?

[•wefgef]

Poti sa te uiti in monitor la sursele trimise in pascal.

[•fogab]

Mea culpa. Am gresit eu. Scuze pt oftici 

PS : 100 fara sa renunt de STL 

[•Robytzza]

Pe testul de pe forum imi da bine ,pe testele mele imi da bine, si totusi iau incorect de ce oare?     

[•Mishu91]

Incearca si testu asta 

Cod:

2
6
0 4
1 4
6 7
3 4
2 4
4 5
7
-100 100
1 2
3 4
1 3
89 90
23 56
12 13

[•Robytzza]

dap  eu nu sortam si nu mai aveam cum sa unesc alea 2 intervale de la primul test ms andrei 

[•ctlin04]

ajutatima va rog, programul meu in turbo pascal merge pentru orice test, chiar si pentru testul cela mare din comentarii merge corect in 0.1 sec., dar in free pascal cind dau programul la executie, imi apare mesajul "exited with exit code 201"

[•savim]

Cred ca eroarea pe care o primesti se datoreaza unui segmentation fault.

Uite un thread care ar putea sa te ajute.

[•jumper007]

Imi poate spune si mie cineva ce e gresit in codul meu ?
Nu inteleg care ar putea fi problema (poate afisarea pe rand nou a solutiilor?...).

Multumesc anticipat

PS: Rezultatele par a fi ok din ceea ce am vazut eu ca si teste..
PS2: Ar putea cineva sa imi puna la dispozitie testul oficial (sau alte teste pe care sa le incerc) ?

Cod:

#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int n, T;
ifstream in("linterv.in");
ofstream out("linterv.out");

class Interval{
	long long a, b;

	public:
		inline long long getA() const { return a; }
		inline long long getB() const { return b; }
		friend bool operator<(const Interval&, const Interval&);
		friend istream& operator>>(istream&, Interval&);
};

bool operator<(const Interval& x, const Interval& y){
	return x.getA() < y.getA();
}


istream& operator>>(istream& is, Interval& inter){
	is >> inter.a >> inter.b;
	return is;
}

void readData(vector<Interval>& Io, Interval& inter){
	Io.clear();

	if (in && !in.eof()){
		in >> n;
	}

	for (int i = 0; i < n; i++){
		in >> inter;
		Io.push_back(inter);
	}
}

void processAndWrite(vector<Interval>& Io){
	int L = 0, X = INT_MIN;
	sort(Io.begin(), Io.end());
	size_t i = Io.size()-1;

	for (int j = 0; j < i; j++){
		
		if (Io[j].getA() >= X){
			L += Io[j].getB() - Io[j].getA();
			X = Io[j].getB();
		}
		else
			if (Io[j].getA() < X && Io[j].getB() <= X){
				continue;
			}
			else
				if (Io[j].getA() < X && Io[j].getB() > X){
					L += Io[j].getB() - X;
					X = Io[j].getB();
				}
	}

	out << L << "\n";
}

int main(int argc, char *argv[]){
	vector<Interval> Int;
	Interval inter;
	in >> T;
	do{
		readData(Int,inter);
		processAndWrite(Int);
		T--;
	}while (T > 0);
	return 0;
}

[•repp4radu]

In primul rand, incearca sa faci o implementare mai simpla, in primul rand. A ta mi se pare foarte greu de urmarit.
Ce mi-a sarit in ochi este faptul ca tu te duci cu j de la 0 pana la Io.size() - 2. Cred ca ar fi corect sa mergi pana la Io.size() - 1.

Hope it helps

[•jumper007]

Am gasit problema. Si apropo, Io.size()-1 am scris... Thanks anyways.

[•repp4radu]

size_t i = Io.size()-1;
for (int j = 0; j < i; j++)
=> faci parcurgerea de la 0 la Io.size() - 2.

Oricum daca ai gasit nu mai conteaza 

[•atatomir]

Am si eu cateva intrebari:
1. Intervalele sunt date in ordine (x,y) cu x<y?
2. Intervalele sunt date in ordine ? (adica daca avem intervalele [x1,y1] si [x2,y2] atunci avem x1 < x2?)

Multumesc mult!

[•SebiSebi]

1. DA.
2. NU.
Succes! 

[•atatomir]

Mutumesc!

[•chimistu]

Pot sa dau un hint celor folosesc pentru aceasta problema vector de pair?
Aveti grija unde declarati vectorul, daca vreti sa nu aveti probleme cu timpul. Desi daca stau mai bine sa ma gandesc ar fi o regula general valabila, indiferent de ce metode folositi

[•Johny_Depp22]

Pot sa dau un hint celor folosesc pentru aceasta problema vector de pair?
Aveti grija unde declarati vectorul, daca vreti sa nu aveti probleme cu timpul. Desi daca stau mai bine sa ma gandesc ar fi o regula general valabila, indiferent de ce metode folositi

si unde mai exact ar trebui sa il declaram?

[•SebiSebi]

Daca declari, in general, vectori in stiva (adica local) programul o sa mearga mai repede, dar trebuie sa ai grija sa nu iesi din limita de memorie pentru stiva.

[•Johny_Depp22]

multumesc! nu stiam asta, dar de acum o sa tin minte

[•BLz0r]

Mie imi da bine pe testul lui fireatmyself (indiferent ca am pus 544 sau 546 ) si totusi imi da WA pe testul oficial...

[•otniel]

ce este gresit imi da incorect

Cod:

#include<iostream>
using namespace std;
#include<stdio.h>
#include<algorithm>
FILE *f,*g;
int i,j,n,t;
long long l,x=-1000010;
struct puncte
{
    long a,b;
};
long cmp(puncte a,puncte b)
{
    return a.a<b.a;
}

puncte q[5001];
int main()
{
    f=fopen("linterv.in.txt","r");
    g=fopen("linterv.out.txt","w");
    fscanf(f,"%d\n",&t);
    while(t)
    {fscanf(f,"%d\n",&n);
    for(i=0;i<n;i++)
        fscanf(f,"%ld%ld\n",&q[i].a,&q[i].b);
    sort(q,q+n,cmp);
    for(i=0;i<n;i++)
         if(q[i].a>=x)
            {x=q[i].b;
         l=l+q[i].b-q[i].a;}
         else
            if(q[i].a<x&&q[i].b>x)
            {l=l+q[i].b-x;
         x=q[i].b;}
        fprintf(g,"%lld\n",l);
        t--;
        for(i=0;i<n;i++)
            cout<<q[i].a<<" "<<q[i].b<<endl;
    }

}

[Editat de moderator]: Foloseste tagul [ code ], [ /code ]

[•alex_bucevschi]

mie imi ia testul din exemplu si testul din comentarii dar imi da WA si nu inteleg de ce?

Cod:

 #include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("linterv.in");
ofstream fout("linterv.out");
int t,i,j,n,x,y,mini,sol;;
void rezolvare()
{
    vector<pair<int,int> >a;
    vector<pair<int,int> >::iterator it;
    fin>>n;
    for(j=1;j<=n;j++)
    {
        fin>>x>>y;
        a.push_back(make_pair(y,x));
    }
    sort(a.begin(),a.end());
    it=a.end()-1;
    mini=it->second;
    sol+=it->first-it->second;
    it--;
    for(;it>=a.begin();it--)
    {
        if(mini<it->first&&mini>it->second)
        {
            sol+=mini-it->second;
            mini=it->second;
        }
        else
        {
            if(mini>it->second)
            {
                mini=it->second;
                sol+=(it->first-it->second);
            }
        }
    }
    fout<<sol<<'\n';
}
int main()
{
    fin>>t;
    for(i=1;i<=t;i++)
    {
        rezolvare();
    }
    return 0;
}

[•otniel]

Cod:

#include<iostream>
using namespace std;
#include<stdio.h>
#include<stdlib.h>
FILE *f,*g;
int n,i,j,t;
struct punct
{
    long long a,b;
};
punct c[5005];
int aux[5005];
long long num;
int tu(int p,int m,int q)
{punct b[5005];
    int i1=p,i2=m+1,x=0;
    while(i1<=m&&i2<=q)
    {
        if(c[i1].a<c[i2].a)
        {
            b[x]=c[i1];
            x++;
            i1++;
        }
        else
            if(c[i1].a>c[i2].a)
        {
            b[x]=c[i2];
            x++;
            i2++;
        }
        else
        {
            if(c[i1].b<c[i2].b)
            {
                b[x]=c[i1];
                x++;
                i1++;
            }
            else
            {
                b[x]=c[i2];
                x++;
                i2++;
            }
        }
    }
    while(i1<=m)
    {
        b[x]=c[i1];
        x++;
        i1++;
    }
    while(i2<=q)
    {
        b[x]=c[i2];
        x++;
        i2++;
    }
    for(int z=p;z<=q;z++)
    c[z]=b[z-p];
}
int io(int p,int q)
{
    if(p<q)
    {
        int mij=(p+q)/2;
        io(p,mij);
        io(mij+1,q);
        tu(p,mij,q);
    }
}
int main()
{
    f=fopen("linterv.in","r");
    g=fopen("linterv.out","w");
    fscanf(f,"%d",&t);
    while(t)
    {i=0;
     i++;
     num=0;
       fscanf(f,"%d",&n);
       for(i=1;i<=n;i++)
       fscanf(f,"%lld%lld",&c[i].a,&c[i].b);
      io(1,n);
      int x=1;
       for(i=2;i<=n;i++)
        {if(i==x)
        i++;

            if(c[i].b>=c[x].b&&aux[i]==0&&c[i].a<=c[x].b)
                {
                    if(c[i].b-c[x].b<0)
                num=num-(c[i].b-c[x].b);
                else
                    num=num+c[i].b-c[x].b;
            aux[i]=1;}
            else
                if(c[i].b<=c[x].b&&c[i].a>=c[x].a)
                aux[i]=1;
                else
                    if(c[i].a>=c[x].b)
                    {x++;
                    i--;
                    }

        }
        for(i=1;i<=n;i++)
           if(aux[i]==0)
            {
                if(c[i].b-c[x].b<0)
                    num=num-(c[i].b-c[x].b);
                else
                    num=num+c[i].b-c[x].b;
            }
           fprintf(g,"%lld",num);
            for(i=1;i<=n;i++)
                {aux[i]=0;
            c[i].a=c[i].b=0;
            }
            n=0;
    t--;
    }
}