.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » maxq

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
maxq


Timp maxim de execuţie / test:
2s
Memorie totala disponibilă / stivă:
32MB / 1MB

Johnie a început să se joace cu un vector de numere. El dispune iniţial de un vector V cu N numere întregi (numerotate de la 0 la N-1) şi poate efectua următoarele operaţii:
- schimbarea elementului de pe poziţia p cu un alt număr întreg;
- aflarea subsecvenţei de sumă maximă din V inclusă între indicii a şi b;

Cerinţă

Ajutaţi-l pe Johnie să efectueze repede operaţiile de mai sus.

Date de intrare

Fişierul de intrare maxq.in conţine pe prima linie numărul N reprezentând dimensiunea vectorului. Pe următoarea linie se găsesc N elemente reprezentând valorile iniţiale ale vectorului. Urmatoarea linie conţine M, reprezentând numărul de operaţii. Pe fiecare dintre următoarele M linii sunt descrise cele M operaţii în forma următoare:
- “0 i p”: numărul 0 de la început codifică faptul că operaţia curentă este una de schimbare; astfel elementul de pe poziţia i a vectorului se înlocuieşte cu numarul întreg p;
- “1 a b”: numărul 1 de la început codifică faptul că operaţia curentă este o întrebare; astfel se cere să se afle subsecvenţa de sumă maximă din vector inclusă între indicii a şi b (a≤b);

Date de ieşire

Fişierul de ieşire maxq.out trebuie să conţină un număr de linii egal cu numărul de întrebări din fişierul de intrare. Pe linia i se cere să se afişeze un singur număr reprezentând suma maximă ce se poate obţine în contextul întrebării i din fişierul de intrare (i=1,2,...); în cazul în care vor exista doar subsecvenţe de sumă negativă se va afişa 0.

Restricţii

1 ≤ N ≤ 200000;
1 ≤ M ≤ 200000;

toate elementele vectorului aparţin intervalului [-100000, 100000];
definim o subsecvenţă ca fiind un şir de termeni consecutivi din vector, iar suma ei se obţine adunând elementele ce o compun;
există cel puţin o întrebare.
pentru 20% din teste se garantează N ≤ 5000

Exemple

maxq.inmaxq.outExplicaţii
5 1 10 4 1 9 4 1 0 3 0 1 1 1 0 3 1 2 4 4 6 12 Pentru prima întrebare se alege subsecvenţa formată de elementul pe poziţia 2 din vector. Pentru a 2-a întrebare se aleg primele 3 elemente din vector (elementul de pe poziţia 1 a fost schimbat). Pentru a 3-a întrebare se aleg toate elementele din intervalul cerut.

autor: Stud. Daniel Păsăilă
propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Articole recomandate
Probleme recomandate
De la ONI 2007: ceas, numere4, cifru, oua, turn, div3, jeton, politic, trecere, agitatie, lacuri, secv, sotron, triunghi, apel, castel, excursia, matricea, randuri, zidar, desc, felinar, joc6, log, tric, cover, dist, munte1, promo, puncte1, role
De acelaşi autor: matrice2, bile2, johnie, cuburi
Despre recursivitate: tren, mere, chimie, sarpe, soldati, formule, infinit, compress, ploaia, cartoane, sub, metro, windows, lacuri, apel, pav, joc11, paianjen, suma2, monkey, csir, lsort, imagine, dir, desert, echitabil, rez, logic, gradina, links, dreptunghiuri, expresie1, cumpanit, reziston, antitero, sablon3
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
Despre arbori: bonuri, tgv, barfa, votare, arce, balaur, trains, bile2, vmem, plopi, caravane, mese, strict, tree, sub, kinder, firma1, albinuta, rlcs, masina, omizi, concurs1, latime, piloti, barca1, arbnr, sirag1, pikachu, arb, logn, arbore, bcast, mesaj1, traseu, asmax, salvare, tramvai1, omida, sediu, string, tv, izo, zoo, ratina, vitale, camion1, arbfind, cezar1, tcast, dep, curent, spp, frunze, sea2, culori, color, urgenta, nori, treegame, antipatie, scanduri, minuni, arb1, activ, regat, kdtree, autostrazi, carray, trenuri1, arbgraf, war, mess, secvnumber, subs, posta, radare, arbore1, hacker, lista, codarb, subsecvente, confuzie, transform, arbsum, copaci3, arbvalmax
Despre recurenţă: nrbun2, nrbun, grupe, palind, siruri, vecini, net, pioni, sir2, perm, red, sume3, pavaj, div3, descfib, robot1, soldati1, expresii, agitatie, aparitii, apel, randuri, zidar, log, cover, dist, munte1, sir1, vizibil, csir, puncte2, aranjari, numere5, anticip, bsir, evantai, sg1, zumzi, lant, perfect, cifru2, numere8, poarta, pviz, poli, desert, echitabil, patrate6, kperms, jump, petrecere, rege, triunghi3, sir9, arbore1, fibgcd, cds, wg, module, nr0, cover1, culori1, 2ndesc, flori2, cntgcd, 2sah, matcnt, nmult
surse trimise | ajutor