Ok. Multumesc mult de solutie

Ideea pare buna insa nu stiu daca se mai poate implementa daca problema este interactiva (numarul de operatii nu este cunoscut de la inceput) 

Atunci nu am inteles eu solutia ta. Cum pot sa impart queryurile in bucati de sqrt de M daca nu le cunosc numarul? Tot ce stiu este ca sunt N operatii care trebuie executate in ordine.

Ai inteles bine enuntul. Insa problema e ca acele queryuri sunt intercalate. Sunt N operatii care pot fi de tipul 1,2 sau 3, lucru pe care am uitat sa il specific 

Salut. As vrea sa stiu daca problema urmatoare are alta solutie mai optima:

Fie un arbore. Initial toate nodurile au aceeasi valoare, mostenite de la radacina. Se fac urmatoarele operatii pe arbore:
1. nodul x ia valoarea y, caz in care toate nodurile din subarborele cu radacina in x care il mostenesc iau valoarea y.
2. seteaza nodul x sa mosteneasca parintele (caz in care se poate modifica valoarea nodului x => operatia 1)
3. aflarea valorii nodului x

Prima solutie care imi vine in minte este ca pentru operatia 1 si 2 sa parcurg subarborele si sa setez valorile, iar aflarea valorii unui nod sa fie in O(1). Exista o solutie mai eficienta, atat din pt de vedere al timpului cat si al memoriei ?
Multumesc anticipat.

+1 pentru postul lui Bogdan si Vlad Gavrila  .
Stau de ceva timp pe topicul asta si m-am hotarat sa va impartasesc si experienta mea. Ma pot mandri cu faptul ca am ratat ONI-ul de anul asta din cauza ca am incurcat fisierele de input si output. E o greseala copilareasca dar foarte costisitoare. Aici nu pot acuza sistemul pentru lipsa mea de experienta.

Eu nu vreau sa dau vina pe sistem pentru greselile mele, ci doar vreau sa se imbunatateasca ceva.

Singurele imbunatatiri pe care le vad eu la sistemul actual sunt:
1) 2 zile de baraj pentru selectia cat mai buna a lotului
2) Un sistem care sa iti evalueze sursa pe exemplele din enunt. Asta numai la nivel de OJI deoarece ii poate ajuta pe incepatori si le da o sansa in plus sa se califice la ONI. Astfel greselile stupide aparute in urma lipsei de experienta pot fi diminuate. La nivel de ONI nu ii vad rostul. Daca ai pretentia sa fii printre primii pe tara in generatia ta si totusi ratezi o clasare buna din cauza greselilor de implementare atunci locul tau nu e acolo. Degeaba esti foarte bun 364 de zile din 365 daca in acea zi in care e nevoie de tine gresesti. ( Poate par prea extremist dar asa privesc eu lucrurile ).

3) Sa li se ofere primilor clasati la ONIbyNet de la fiecare clasa sansa sa participe la baraj ( pe banii lor sau finantati de minister ). Astfel cei care sunt foarte buni si au ratat ONI-ul din diverse motive mai au o sansa in plus. Din cate stiu, acum ceva timp era posibil asa ceva.

Totusi voi aveti 8-9 ani de experienta si ati avut timp sa invatati din greseli.

Aici Petru, iti dau dreptate. Este clar ca cei care au inceput informatica in gimnaziu au un avantaj urias. Singura posibilitate pe care o vad eu  de a recupera  este sa participi la cat mai multe concursuri onsite ( la cele online emotiile si stresul au un impact mult mai mic ). Din pacate sunt regiuni in care nu vezi decat 1-2 concursuri organizate anual ( in zona judeteului Suceava: Stefan Dartu din Vatra-Dornei si cel organizat de CN Piatra Neamt).

Si articolul asta e de folos: http://infoarena.ro/concursul-de-informatica. Btw, cred ca cel mai mult conteaza starea ta de spirit din timpul si inaintea concursului. De obicei "lupta intre marii campioni se da la emotii" . Bafta

Duminica ar fi cel mai bine. Pe 15-16 are loc alt concurs de informatica la Vatra Dornei  .

Pe 15(sambata) este concursul

Si pe 16(duminica) e premierea  .

Duminica ar fi cel mai bine. Pe 15-16 are loc alt concurs de informatica la Vatra Dornei  .

Cand se da update la rating? 

Problemele se adauga in arhiva tot miercuri?

Sursele trimise  cat timp evaluarea este privata vor fi luate in considerare?

Ce viteza are fata?

Fata de unde incepe deplasarea?

Cred ca trebuie marita putin limita de timp. Am implementat o solutie cu normalizare( cu lower_bound) + AIB + parsare si iau tle pe testul 9.

Permutarea este una a elementelor 1, 2, .. N sau a N elemente A1, A2, .. An?

Ah, Multumesc  . Nu imi inchipuiam ca fstream include atat de multa memorie  .

Cred ca este ceva in neregula cu limita de memorie. Tot ceea ce declar este:

Cod:

bitset<18>res[100001];
char ans[130000];

plus cateva inturi, ceea ce inseamna circa 300 Kb. Si limita este de 640 Kb  .

Nu se poate mari limita de timp? Am facut dinamica cu memoizare + parsare si tot nu intra.

Bafta multa si sa aveti un IOI cat mai bogat in medalii     

Multumesc de raspuns  . Si inca o intrebare. Acel financial aid este nerambursabil?

Si in SUA reprezinta un factor decisiv? Adica daca ai media pe cei 4 ani de liceu sub 9 nu mai esti admis?

La admitere conteaza notele din liceu sau nota de la BAC?

Felicitari organizatorilor  . Am o intrebare: Cand se da update la ratinguri?

Nu ar trebui micsorata limita de timp    ? Sursa mea  http://infoarena.ro/job_detail/733433 merge sub 200 ms.