InfoAs Atlas

<- Go back View preview

Problema Cate numere in interval

Identification properties

🔒 The following are read-only properties. If you wish to change them, please create a new problem.

Name

Content ID

Hash Note: The hash is stored in the filesystem.

Content properties

Task

Examples

Default code

Summary

Editorial

**Observație.** O soluție care parcurge, pentru fiecare interval dintre cele `m`, elementele șirului `a` este ineficientă: în cel mai rău caz se fac `2 * n * m` operații, un număr prea mare pentru limita de timp. Așadar, se caută soluții alternative.

**Soluția recomandată.** Se utiliează algoritmul de căutare binară. Ordonăm elementele lui `a` în ordine crescătoare, deoarece ne ajută mult și totodată nu strică cu nimic rezultatul. De aici, putem să căutăm binar pozițiile unde s-ar afla `x` și `y` în `a` (există posibilitatea ca `x` și `y` să nu se afle în șir, însă cu siguranță se vor afla între două valori din șir; `x` se numește _lower bound_ , iar `y` se numește _upper bound_). Scădem poziția mai mică din cea mai mare, acesta fiind rezultatul pentru intervalul curent. Complexitatea finală:` O(m * log<sub>2</sub>n)`.

Pentru ordonarea elementelor lui `a` în ordine crescătoare se recomandă folosirea funcției `sort()` din biblioteca `<algorithm>`, sau orice algoritm de sortare care sortează în timp logaritmic (deoarece șirul `a` este foarte mare).

Solution

Contributor ID

Author

Tags

Problem set

Chapter ID

Published At

Admin Approved

Difficulty

License

File name	Description	Updated at	Size	Actions
hash.txt	Special file The hash of all the content of a problem. Autogenerated.	10 January 2025 21:26	64 B	View
manifest.json	Special file Metadata for the problem. Autogenerated.	10 January 2025 21:26	992 B	View
0-cate-numere-in-interval.in	/ 100	10 January 2025 21:26	32 B	View
0-cate-numere-in-interval.ok	/ 100	10 January 2025 21:26	7 B	View
1-cate-numere-in-interval.in	/ 100	10 January 2025 21:26	871 KB	View
1-cate-numere-in-interval.ok	/ 100	10 January 2025 21:26	169 KB	View
2-cate-numere-in-interval.in	/ 100	10 January 2025 21:26	742 KB	View
2-cate-numere-in-interval.ok	/ 100	10 January 2025 21:26	100 KB	View
3-cate-numere-in-interval.in	/ 100	10 January 2025 21:26	753 KB	View
3-cate-numere-in-interval.ok	/ 100	10 January 2025 21:26	106 KB	View
In total: 10 files 2 MB

View files grouped by their test cases.

Index	Input file	Output file	Score	Visibility

Enzo Judge

Offline

Server is offline.

Fernando Judge

Offline

Server is offline.

Main Instance

Offline

Server is offline.

Judge count: 2 Instance count: 1

Online judges will be synchronised with all the files. The previous version(s) of the problem will be overwritten.

Problema Cate numere in interval

Identification properties

Content properties

Technical properties

Delete all files