Submission #628552

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
628552	2022-08-13 13:21:40	dqhungdl	Radio Towers (IOI22_towers)	C++17	15 / 100	4059 ms	9296 KiB

towers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 5;
int N, maxH[MAX][20];
bool isMountain = true;
vector<int> H;
int get(int l, int r) {
    int k = log2(r - l + 1);
    return max(maxH[l][k], maxH[r - (1 << k) + 1][k]);
}
void init(int _N, vector<int> _H) {
    N = _N, H = _H;
    for (int i = 0; i < N; i++)
        maxH[i][0] = H[i];
    for (int t = 1; t <= 18; t++)
        for (int i = 0; i + (1 << t) - 1 < N; i++)
            maxH[i][t] = max(maxH[i][t - 1], maxH[i + (1 << (t - 1))][t - 1]);
    int id = max_element(H.begin(), H.end()) - H.begin();
    for (int i = id; i > 0 && isMountain; i--)
        isMountain &= (H[i] > H[i - 1]);
    for (int i = id; i < N - 1 && isMountain; i++)
        isMountain &= (H[i] > H[i + 1]);
}
int max_towers(int L, int R, int D) {
    if (isMountain)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 4 / 4
• Subtask 2: 11 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23