InfoAs Atlas

<- Go back View preview

Problema Leftmax

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

În clasa lui Dexter sunt `N` elevi de înălțimi distincte. La ora de sport, ei sunt așezați în linie, de la stânga la dreapta. Profesorul lor, Johnny, va selecta pentru un exercițiu elevi aflați pe poziții consecutive în linie, astfel încât cel mai înalt elev dintre cei selectați să se afle în prima jumătate a acestora.  
  
De exemplu, dacă elevii au, în ordine, înălțimile `1, 5, 4`, atunci profesorul poate să îi selecteze pe cei cu înălțimile `5` și `4`, dar nu poate să îi selecteze pe cei cu înălțimile `1` și `5`. Desigur, există mai multe moduri de a selecta elevii astfel încât să fie satisfăcută condiția de mai sus. Profesorul Johnny ar vrea să afle în câte moduri se poate face acest lucru.

## Cerință

Dându-se `N` și înălțimile elevilor din clasă, aflați în câte moduri pot fi selectați oricâți elevi aflați pe poziții consecutive, astfel încât să fie îndeplinită condiția din enunț. 
## Date de intrare

Fișierul de intrare `leftmax.in` conține pe prima linie numărul `N`, iar pe a doua linie înălțimile elevilor în ordinea în care sunt așezați în linie. 
## Date de ieșire

Fișierul de ieșire `leftmax.out` va conține pe prima linie răspunsul la cerință, sub formă de rest al împărțirii la `1.000.000.007` (`modulo 1.000.000.007`). 
## Restricții și precizări

* `1 ≤ N ≤ 100.000`
  * `1 ≤ înălțimea oricărui elev ≤ N`
  * Dacă se selectează un număr impar de elevi, atunci considerăm că cel din mijlocul selecției se află în prima jumătate a elevilor selectați
  * Pentru 10 puncte, `N ≤ 1.000` și elevii sunt ordonați descrescător după înălțime
  * Pentru alte 35 de puncte, `N ≤ 1.000`
  * Pentru alte 20 de puncte, `N ≤ 30.000`

Examples

[{"input": "4\n1 4 2 3", "output": "8", "explanation": "Pentru primul exemplu: sunt <code>4</code> moduri de a selecta c\u00e2te un singur elev. Este un singur mod de a selecta c\u00e2te doi elevi (cei cu \u00een\u0103l\u021bimile <code>4</code> \u0219i <code>2</code>). Sunt <code>2</code> moduri de a selecta c\u00e2te <code>3</code> elevi (cu \u00een\u0103l\u021bimile <code>4, 2, 3</code>, sau <code>1, 4, 2</code>). Este un singur mod de a selecta to\u021bi cei <code>4</code> elevi. \u00cen total sunt <code>8</code> moduri. Pentru al doilea exemplu: se poate selecta doar c\u00e2te un singur elev. Pentru al treilea exemplu: se pot selecta oric\u00e2\u021bi elevi pe pozi\u021bii consecutive."}, {"input": "7\n1 2 3 4 5 6 7", "output": "7", "explanation": "Pentru primul exemplu: sunt <code>4</code> moduri de a selecta c\u00e2te un singur elev. Este un singur mod de a selecta c\u00e2te doi elevi (cei cu \u00een\u0103l\u021bimile <code>4</code> \u0219i <code>2</code>). Sunt <code>2</code> moduri de a selecta c\u00e2te <code>3</code> elevi (cu \u00een\u0103l\u021bimile <code>4, 2, 3</code>, sau <code>1, 4, 2</code>). Este un singur mod de a selecta to\u021bi cei <code>4</code> elevi. \u00cen total sunt <code>8</code> moduri. Pentru al doilea exemplu: se poate selecta doar c\u00e2te un singur elev. Pentru al treilea exemplu: se pot selecta oric\u00e2\u021bi elevi pe pozi\u021bii consecutive."}, {"input": "7\n7 6 5 4 3 2 1", "output": "28", "explanation": "Pentru primul exemplu: sunt <code>4</code> moduri de a selecta c\u00e2te un singur elev. Este un singur mod de a selecta c\u00e2te doi elevi (cei cu \u00een\u0103l\u021bimile <code>4</code> \u0219i <code>2</code>). Sunt <code>2</code> moduri de a selecta c\u00e2te <code>3</code> elevi (cu \u00een\u0103l\u021bimile <code>4, 2, 3</code>, sau <code>1, 4, 2</code>). Este un singur mod de a selecta to\u021bi cei <code>4</code> elevi. \u00cen total sunt <code>8</code> moduri. Pentru al doilea exemplu: se poate selecta doar c\u00e2te un singur elev. Pentru al treilea exemplu: se pot selecta oric\u00e2\u021bi elevi pe pozi\u021bii consecutive."}]

Default code

Summary

Editorial

**Complexitatea**`**O(N** **3** **)**`**: 15 puncte**

Pentru această complexitate, putem considera toate subsecvențele de elevi consecutivi, să găsim elevul de înălțime maximă iterând prin elementele secvențelor. Rămâne doar să numărăm câte subsecvențe satisfac condiția din enunț.

**Complexitatea**`**O(N** **2** **)**`**: 45 puncte**

Pentru această complexitate, pornim de la soluția de 15 puncte, dar observăm că, dacă parcurgem subsecvențele în ordine crescătoare după poziția primului elev din subsecvență, iar în caz de egalitate în ordine crescătoare după poziția ultimului elev din subsecvență, atunci putem să aflăm poziția elevului de înălțime maximă în timp constant pentru fiecare subsecvență. Acest lucru se datoarează faptului ca elevul de înălțime maximă printre cei de la al `i`-lea până la al `(j + 1)`-lea elev este fie cel de înălțime maximă printre cei de la al `i`-lea până la al `j`-lea elev (pe care deja îl cunoaștem), fie fix elevul de pe poziția `j + 1`.

**Complexitatea**`**O(N)**`**: 100 puncte**

Vom stoca înălțimile copiilor într-un vector. Într-o primă fază, putem folosi o stivă pentru a calcula două șiruri `st` și `dr` unde `st(i)` reprezintă poziția cea mai mică `j` pentru care toți copiii între `j` și `i` sunt mai mici sau egali cu cel pe poziția `i`, și `dr(i)` reprezintă poziția cea mai mare `j` pentru care toți copiii între `i` și `j` sunt mai mici sau egale cu cel pe poziția `i`. Această precalculare poate fi realizată în timp linear.

Acum, iteram prin șir. Când suntem la poziția `i` considerăm toate subsecvențele de copii pentru care copilul cel mai înalt este pe poziția `i`. Din definitia lui `st`, `dr` reiese că, dacă subsecvențele acestea sunt de la al `x`-lea copil la al `y`-lea copil, atunci `st(i) ≤ x ≤ i ≤ y ≤ dr(i)`. Pe noi ne intereseaza acele subsecvențe unde, mai mult, avem că `i - x ≤ y - i`. Daca notam pe `i - st(i)` cu `L` și pe `dr(i) - i` cu `R` atunci se poate demonstra că sunt

* `(min(L, R) + 1) * (R - L + 2 + max(R, L)) / 2`

Formula se demonstrează astfel:

Luăm două cazuri, unul unde `L ≤ R`, unul unde `L > R`.

1. Dacă `L ≤ R` atunci formula devine `(L + 1) * (2 * R - L) / 2`. În cazul acesta, putem fixa pe `i - x` de la `0` la `L`, iar pentru fiecare mod de a îl fixa, putem fixa pe `y - i` de la `i - x` la `R`. Astfel, vrem suma progresiei aritmetice cu `L + 1` termeni unde primul termen este `R`, iar ultimul termen este `R - L`, adică fix formula dată mai sus;
  2. Dacă `L > R`, atunci formula devine `(R + 1) * (R + 2) / 2`. În cazul acesta, putem fixa pe `y - i` de la `0` la `R`, iar pentru fiecare mod de a il fixa, putem fixa pe `i - x` de la `0` la `y - i`. Astfel, vrem suma progresiei aritmetice cu `R + 1` termeni unde primul termen este `1` iar ultimul termen este `R + 1`, adica fix formula data mai sus.

Tot ce rămâne acum este însumarea acestora pentru toate valorile lui `i`.

Solution

```
/// sursa oficiala 100p O(N)
/// student Tamio-Vesa Nakajima
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using cd = complex<double>;

int main(){
 ifstream f("leftmax.in");
 ofstream g("leftmax.out");
 
 // Citim inputul.
 int n;
 f >> n;
 vector<int> v(n);
 for(auto& x : v)
 f >> x;

// Folosim o stiva pentru a calcula sirurile
 // st si dr din solutie.
 vector<int> st(n), dr(n);
 stack<int> stiva;
 for(int i = 0; i < n; ++i){
 while(!stiva.empty() && v[stiva.top()] < v[i]){
 dr[stiva.top()] = i - 1;
 stiva.pop();
 }

st[i] = (stiva.empty() ? 0 : stiva.top() + 1);
        stiva.push(i);
    }
    while(!stiva.empty()){
        dr[stiva.top()] = n - 1;
        stiva.pop();
    }

// Acum vom itera prin sir, retinand solutia in ret.
 ll ret = 0;
 for(int i = 0; i < n; ++i){
 const ll L = i - st[i], R = dr[i] - i;
 ret += (min(R, L) + 1) * (R - L + 2 + max(R, L)) / 2;
 }

// Afisam solutia.
 g << ret % 1000000007 << endl;

return 0;
}
```

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	3 KB	View
0-leftmax.in	/ 100	10 January 2025 21:26	692 B	View
0-leftmax.ok	/ 100	10 January 2025 21:26	6 B	View
1-leftmax.in	/ 100	10 January 2025 21:26	696 B	View
1-leftmax.ok	/ 100	10 January 2025 21:26	6 B	View
2-leftmax.in	/ 100	10 January 2025 21:26	656 B	View
2-leftmax.ok	/ 100	10 January 2025 21:26	5 B	View
3-leftmax.in	/ 100	10 January 2025 21:26	13 KB	View
3-leftmax.ok	/ 100	10 January 2025 21:26	8 B	View
4-leftmax.in	/ 100	10 January 2025 21:26	13 KB	View
4-leftmax.ok	/ 100	10 January 2025 21:26	8 B	View
5-leftmax.in	/ 100	10 January 2025 21:26	13 KB	View
5-leftmax.ok	/ 100	10 January 2025 21:26	8 B	View
6-leftmax.in	/ 100	10 January 2025 21:26	13 KB	View
6-leftmax.ok	/ 100	10 January 2025 21:26	8 B	View
7-leftmax.in	/ 100	10 January 2025 21:26	13 KB	View
7-leftmax.ok	/ 100	10 January 2025 21:26	8 B	View
8-leftmax.in	/ 100	10 January 2025 21:26	13 KB	View
8-leftmax.ok	/ 100	10 January 2025 21:26	8 B	View
9-leftmax.in	/ 100	10 January 2025 21:26	164 KB	View
9-leftmax.ok	/ 100	10 January 2025 21:26	10 B	View
10-leftmax.in	/ 100	10 January 2025 21:26	164 KB	View
10-leftmax.ok	/ 100	10 January 2025 21:26	10 B	View
11-leftmax.in	/ 100	10 January 2025 21:26	164 KB	View
11-leftmax.ok	/ 100	10 January 2025 21:26	10 B	View
12-leftmax.in	/ 100	10 January 2025 21:26	164 KB	View
12-leftmax.ok	/ 100	10 January 2025 21:26	9 B	View
13-leftmax.in	/ 100	10 January 2025 21:26	575 KB	View
13-leftmax.ok	/ 100	10 January 2025 21:26	10 B	View
14-leftmax.in	/ 100	10 January 2025 21:26	575 KB	View
14-leftmax.ok	/ 100	10 January 2025 21:26	10 B	View
15-leftmax.in	/ 100	10 January 2025 21:26	575 KB	View
15-leftmax.ok	/ 100	10 January 2025 21:26	10 B	View
16-leftmax.in	/ 100	10 January 2025 21:26	575 KB	View
16-leftmax.ok	/ 100	10 January 2025 21:26	10 B	View
17-leftmax.in	/ 100	10 January 2025 21:26	575 KB	View
17-leftmax.ok	/ 100	10 January 2025 21:26	10 B	View
18-leftmax.in	/ 100	10 January 2025 21:26	10 B	View
18-leftmax.ok	/ 100	10 January 2025 21:26	2 B	View
19-leftmax.in	/ 100	10 January 2025 21:26	16 B	View
19-leftmax.ok	/ 100	10 January 2025 21:26	2 B	View
In total: 42 files 3 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 Leftmax

Identification properties

Content properties

Technical properties

Delete all files