| Ուղարկել | Բոլոր լուծումները | Լավագույն լուծումները | Վերադառնալ ցուցակին |
SEGMENTS22 - Կարենը և միջակայքերը |
Կարենը շատ էր ուզում հայտնվել խնդիրներից մեկում: Այդ պատճառով Համլետը որոշեց նրան տալ n երկարությամբ, ամբողջ թվերի a1, a2, ... , an զանգված, և եթե նա կարողացավ հաշվել այդ զանգվածի գեղեցիկ միջակայքերի քանակը, ապա նա կլինի խնդիրներից մեկի հերոսը։
a զանգվածի [l,r] (1 ≤ l < r ≤ n) միջակայքը համարվում է գեղեցիկ եթե՝
al=ar- Կամայական
l < i < rամբողջ թվի համար ճիշտ էai > alանհավասարությունը։
Ինչպես տեսնում եք՝ Կարենը հաջողությամբ ավարտել է առաջադրանքը, բայց առաջադրանքը կատարելը Կարենի համար տևեց մի քանի օր (քանի որ n-ը շատ մեծ էր)։ Կարենը վախենում է, որ հանրապետական փուլից առաջ Համլետը կտա նրան նույն առաջադրանքը և ձեզ խնդրում է գրել ծրագիր, որ կլուծի այս խնդիրը և կօգնի նրան մյուս անգամ ավելի արագ կատարել առաջադրանքը։
Մուտքային տվյալներ
Մուտքի առաջին տողում տրված է n (1 ≤ n ≤ 106) թիվը՝ զանգվածի էլեմենտների քանակը։ Հաջորդ տողում տրված են զանգվածի էլեմենտները՝ a1, a2, ... , an անջատված բացատով։ ( 1 ≤ ai ≤ 109, կամայական 1 ≤ i ≤ n ամբողջ թվի համար)
Ելքային տվյալներ
Պետք է արտածել մեկ թիվ՝ զանգվածի գեղեցիկ միջակայքերի քանակը։
Օրինակ
| Մուտք | Ելք |
|---|---|
| 9 3 5 5 3 2 1 2 1 1 |
4 |
| 6 2 1 3 5 7 1 |
1 |
Բացատրություն
Առաջին օրինակում գեղեցիկ միջակայքերն են՝ [1,4],[2,3],[6,8],[8,9]:
Երկրորդ օրինակում միակ գեղեցիկ միջակայքը [2,6]-ն է:
| Ավելացրեց. | Andreasyan |
| Ամսաթիվ. | 2022-02-06 |
| Ժամանակի սահմանափակումը. | 1s |
| Ծրագրի տեքստի սահմանափակումը. | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Լեզուներ. | C CSHARP C++ 4.3.2 CPP CPP14 JAVA PAS-GPC PAS-FPC PYTHON3 |
| Աղբյուրը. | Մարզային փուլ, 2021-22 |
RSS