vreme!

ljudi, jel moze za 0,1 sekundu da prodje oko 12 530 000 operacija!!!

poz

:D...Zavisi na kom kompu...Za sad takav niko ne poseduje...

koliko si siguran u to?
sta ti mislis: koliko maximalno moze proci za 1 sekund!

poz

Pa stvorio sam procenu vremena izvrsavanja koja mi govori da se oko 1000000 operacija izvrsava za 0,1 sec..No to nije sigurno ali je sigurno da se 12 000 000 operacija ne moze izvrsiti za manje od ,recimo, 0.9-1 sec.
Ta procena me je do sad dobro sluzila...
Poz,

ok! al, to ne mora da znaci da ne moze vise od 1 000 000 operacija za 1s.
jel imas neki dokaz!
hjehjehje
:]
dobro, sta misle ostali ljudi!!!

Napravi si tajmer pa proveri koliko vreme treba za 1000000 operacije.
Osven od kompjuterot, zavisi i od to kakve su operacije, na primer operacije sa realni brojevi se izvrsavaju duze od operacije sa celi brojevi...

Znaci sve je to relativno i zavisi od mnogu faktori. Eto proverio sam za ovaj kod:

for i:= 1 to 12 000 000 do
s:= s + 1;

kad je s integer izvrsava se za 0.06s (znaci renovator, ja imam takav kompjuter :)), a kad je s real izvrsava se 2.14s. Free Pascal je jos brzi od TP, 0.03s i 0.15s.

Nisam znao...Nisam bas zalazio u detalje.
Izvinjavam se na pogresnoj informaciji.

hvala dimitar!
:]

poz

Ma covece ono vreme od 0.1s za zadatak interval i zadatak ministri je uzas.Znaci ova resenja imaju prekoracenje doticnog vremena (kod intervala za poslednjih 4,kod ministara za poslednjih 5 primera)...

[intervali] - resenje 1

...
int n,i,j,k,max;

int tmax[5001];
cin>>n;

for (i=0;i<n;i++)
cin>>t[i].l>>t[i].r;

qsort(t,n,sizeof(inter),sort_function);
j = t[n-1].l;
max = 1;
for (i = n-2;i>=0;--i){
if (t[i].r <= j){
j = t[i].l;
max++;
}
}
cout<<max<<endl;
...

[intervali ] -resenje 2
...
tmax[0] = 1000000;
max = 0;
k=0;
do{
tmax[++k] = - 1000000;
j = n;
for (i=0;i<n;i++)
if (t[i].r <= tmax[k - 1] && t[i].l > tmax[k] ){
tmax[k] = t[i].l;
j = i;
}

t[ j ] = t[n - 1];
n--;
}while (j < n);
cout<<(k-1)<<endl;

[ministri]
...
typedef struct {
int drug;
int poz;
int iter;
} ministar;

...
int i,n,j,k;
ministar m[MAX];
int max;
int curr,iter;

cin>>n;
max = 0;
for (i = 1; i <= n ;++i){
cin>>m[i].drug;
if (m[i].drug == i){
m[i].iter = 0; //oznaci ga kao vec obradjenog 0-ta iteracija za sve sam
sebi najbolji drug
max++;
}
else{
m[i].iter = 666666;
}
}

for (i = 1; i <= n; ++i){
if (m[i].iter == 666666){ //nije obradjivan?
iter++;
curr = 1;
m[i].poz = 0;
m[i].iter = iter;
j = i;
//uvek je j>=0 jer svaki ministar ima nekog najboljeg druga
//ako je drug[j] == j onda je uvek mit[ drug[j] ] == 0
while (m[ m[ j ].drug ].iter == 666666){
j = m[j].drug;
m[j].iter = iter;
m[j].poz = curr;
curr++;
}

if (m[ m[j].drug ].iter == iter)
max += curr - m[ m[j].drug ].poz;

}
}
cout<<max<<endl;
...

Sta to znaci,da bukvalno treba da ne prodjem ni kroz sve ministre 2 puta za zadatak ministri odnosno ne smem da imam O((n+1)*n/2) u najgorem slucaju(za resenje 2) ili O(qs)+O(n) (za resenje 1) u zadatku intervali!?!??!?!

Za nevericu,ili mozda ne!Ako ulazne podatke citam preko standardne scanf fu-je umesto preko cin-a,oba zadatka prolaze bez grca za 0.1 s.Znaci nikako ne koristiti streamove za citanje podataka,vec scanf!!!!