Nu chiar. E O(N log log N). 

Se poate lua 100 cu sortare + cautare binara, dar si cu sortare + O(N)  

OK. Nu ma asteptam sa mearga asa de prost hash-ul, dar se mai intampla.

@ Vlad: Nu set din STL. La puntele din hash. Graba...

LE: Sebi , cred ca e bun rationamentul.

Da, este bun, am luat 40 de puncte cu complexitatea O(n). O sa inlociuesc hash-ul cu o sortare + cautare binara, sa vad cat iau.   

Sper ca am inteles ce vrei sa spui. Daca aveam exemplul din enunt , dar in alta ordine :

Cod:

5 3 10.000000
41.887902
0.000000
12.978671
38.111412
20.943951

l = 20.943951
L = 62.83185
Plecam din primul punct, deoarece pe el nu l-am mai "vizitat" pana acum.
Caut punctul 41.887902 + l=62.83185 , care este egal cu circumferinta cercului, deci scad L - > punctul devine 0.
Caut punctul 0 + l = 20.943951, il gasesc -> am gasit trei puncte care formeaza un triunghi echilateral.
Eu am considerat ca nu conteaza ordinea punctelor.

Am incercat 3 modalitati , insa fara succes. Am pastrat hashing-ul pentru numere reale (cel cu partea fractionala), folsind constanta propusa de Knuth si modulo 10007.

Am gasit L = PI * R * 2 / k, apoi bagam toate punctele intr-un hash. Adaugam L la punctul de start, pana cand gaseam k puncte sau pana gaseam un punct care nu exista. Daca depaseam circumferinta cercului, o scadeam din distanta curenta.
Aveam 132 ms daca faceam doar citirea.  

Felicitari pentru runda! 

Cum ati reusit sa scapati de TLE? Eu am rezolvat-o in O(n) cu hashuri?  

Nu, nu e corect.
Asta se mai intampla si cand faci suma a doua numere , fiecare int, suma care depaseste int.
Trebuie sa scrii:

Cod:

 int a, b;
long long s;
s = 0LL + a + b

sau

Cod:

s = (long long) a + b

Ideea e ca compilatorul executa operatiile pe int, nu conteaza tipul variabilei.

Daca vrei sa faci update pe interval si query tot pe interval treaba devine mai complicata(trebuie sa faci lazy update).
Pentru update pe interval si query numai pentru secventa [1,n] consulta problema http://infoarena.ro/problema/biscuiti.
Succes!

Tu declari variabila s float, dar operatiile se executa pe int. Inlocuieste asta

Cod:

ma=s/n;

cu

Cod:

ma=(float)s/n;

si o sa mearga. Succes!  

dar as vrea sa cunosc si eu omul care a lenevit un an intreg si e capabil sa se adune atat de bine pe ultima suta de metri.)

Cred ca acest articol , http://infoarena.ro/blog/reteta-de-success, ti-ar fi de folos. Succes!

Cred ca ar trebui marita limita de timp. Se poate lua 100 doar cu parsare. Multumesc!

Nu e bine asa. Uite o secventa corecta :

Cod:

  ultim=1;     
  s=1;     
  for(i=2;i<=n;i++)         
         if(v[i].a>=v[ultim].b) {            
                  ultim=i;             
                  s++;         
          }     
  g<<s; 

Problema este o reformulare la "Problema spectacolelor", pe care o gasesti in orice manual.
Sortezi dupa y, iar daca ai mai multe intervale care au acelasi y, le sortezi dupa x. Acum faci greedy (e clar ca intervalul care are y cel mai mic este favorabil sa il alegi,  nu are rost sa alegi altul care se termina mai tarziu).
Succes!

El sorteaza crescator dupa greutate, deci nu mai e nevoie de a doua comparatie.  

L.E. Nu imi dau seama ce ar putea fi gresit. Daca nu reusesti sa revolvi pana la urma, da-mi un PM si iti dau sursa mea.

Principiul e corect. Incearca rezolvarea in O(N²), fara AIB sau AINT, care ia 100p. Succes!

Pentru permutari : http://infoarena.ro/job_detail/668890?action=view-source ;
Pentru submultimi : http://infoarena.ro/job_detail/830055?action=view-source (iti dai tu seama cum sa il modifici ca sa afiseze 0 si 1);
Pentru combinari : http://infoarena.ro/job_detail/830050?action=view-source ;
Succes!

Da. E corect.

Cod:

#include <iostream>
#include <fstream>
  using namespace std;
  int cmmdc(int a,int b)
  {  if (!b) return a;
  return cmmdc(b,a % b);
  }
 int main(void)
 {
    ifstream f("sum.in");
    ofstream g("sum.out");
   int n,x,y,i,j;
   f>>n;
   for(i=1;i<=n;i++)
   {   f>>x;
    y=0;
     for(j=1;j<=2*x;j++)
     {  if (cmmdc(x,j)==1) y=y+j;}
     g<<y<<"\n";
     }
     f.close();
   return 0;
   }

Acum ruleaza. Succes!

In loc de

Cod:

#include <fstream.h>
#include <iostream.h>

Scrie:

Cod:

#include <fstream.h>
#include <iostream.h>
using namespace std;

si o sa mearga. Succes! 

La orice problema parsarea merge mai repede decat citirea caracter cu caracter. 

Adevarat, dar uneori nu se observa, cum este si aceasta problema. Cred ca asta ai vrut sa intrebi Andrei, doar ca ai formulat un big ambiguu. Astfel, pentru limite destul de mari (de la 1 milion incolo), ar cam trebui sa se simta citirea parsata.

Multumesc pentru corectare.

La orice problema parsarea merge mai repede decat citirea caracter cu caracter. 

Problema se rezolva folosind 2 cozi (nu cu o parcurgere in latime simpla). Calculezi mai intai nodurile cu distanta 0 , apoi cele cu distanta 1 , s.a. Merge mai repede asa deoarece rezultatul va fi un numar mic. Succes!