#include <bits/stdc++.h>
using namespace std;
const int c=100005, sok=2e9+5;
int n, t[c], maxi;
bool tc1=1, fontos[c];
set<pair<int, int> > tc5;
set<int> pos;
set<pair<int, int> > dif;
int kul(int a, int b) {
return abs(t[a]-t[b]);
}
void sub(int p) {
auto it=pos.find(p);
int el=0, kov=0;
it++;
kov=(*it);
it--, it--;
el=(*it);
pos.erase(p);
dif.erase({kul(p, kov), p});
dif.erase({kul(el, p), el});
dif.insert({kul(el, kov), el});
}
void calc_tc5() {
fontos[0]=1;
int ut=sok, ans=0, id=1;
for (int i=1; i<=n+1; i++) {
if (id==1) {
ut=max(ut, t[i]);
if (ut>t[i]) {
fontos[i-1]=1;
ut=t[i];
id=0;
ans++;
}
} else {
ut=min(ut, t[i]);
if (t[i]>ut) {
fontos[i-1]=1;
ut=t[i];
id=1;
}
}
}
int el=-1;
for (int i=0; i<=n+1; i++) {
if (!fontos[i]) continue;
pos.insert(i);
if (el!=-1) {
dif.insert({kul(el, i), el});
//cout << "fontos " << el << " " << i << "\n";
}
el=i;
}
tc5.insert({0, ans});
while (ans>1) {
auto it=dif.begin();
int ert=(*it).first, p=(*it).second;
auto it2=pos.upper_bound(p);
int kov=*it2;
sub(p), sub(kov);
ans--;
//cout << ert << " " << ans << "\n";
it=tc5.upper_bound({ert, ans});
if (it!=tc5.end()) tc5.erase(it);
tc5.insert({ert, ans});
}
}
void init(int N, vector<int> sz) {
n=N;
for (int i=0; i<n; i++) {
t[i+1]=sz[i];
if (t[i+1]>t[maxi]) maxi=i+1;
}
t[0]=sok, t[n+1]=sok;
for (int i=1; i<=n; i++) {
if (i<maxi && t[i]>t[i+1] || i>maxi && t[i]>t[i-1]) {
tc1=0;
}
}
calc_tc5();
}
int lassu(int l, int r, int d) {
int ut=t[l]+d, ans=0, id=1;
for (int i=l; i<=r; i++) {
if (id==1) {
ut=max(ut, t[i]);
if (ut-t[i]>=d) {
ut=t[i];
id=0;
ans++;
}
} else {
ut=min(ut, t[i]);
if (t[i]-ut>=d) {
ut=t[i];
id=1;
}
}
}
return ans;
}
int max_towers(int l, int r, int d) {
l++, r++;
if (tc1) {
if (l<=maxi && maxi<=r && max(t[l], t[r])+d<=t[maxi]) return 2;
return 1;
}
if (l==1 && r==n) {
auto it=tc5.upper_bound({d, 0});
it--;
return (*it).second;
}
return lassu(l, r, d);
}
/*
int main()
{
int N;
vector<int> P;
cin >> N;
for (int i=0; i<N; i++) {
int x;
cin >> x;
P.push_back(x);
}
init(N, P);
int q;
cin >> q;
while (q--) {
int l, r, d;
cin >> l >> r >> d;
cout << max_towers(l, r, d) << "\n";
}
return 0;
}
*/
/*
7
6 7 4 5 2 3 1
*/
/*
7
1 2 6 4 5 3 7
*/
Compilation message
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:78:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
78 | if (i<maxi && t[i]>t[i+1] || i>maxi && t[i]>t[i-1]) {
| ~~~~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
350 ms |
988 KB |
Output is correct |
2 |
Correct |
906 ms |
1576 KB |
Output is correct |
3 |
Correct |
847 ms |
1352 KB |
Output is correct |
4 |
Correct |
664 ms |
1360 KB |
Output is correct |
5 |
Correct |
889 ms |
1448 KB |
Output is correct |
6 |
Correct |
749 ms |
1352 KB |
Output is correct |
7 |
Correct |
845 ms |
1436 KB |
Output is correct |
8 |
Correct |
1 ms |
208 KB |
Output is correct |
9 |
Correct |
1 ms |
208 KB |
Output is correct |
10 |
Correct |
1 ms |
208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
2 ms |
336 KB |
Output is correct |
3 |
Correct |
2 ms |
336 KB |
Output is correct |
4 |
Correct |
2 ms |
464 KB |
Output is correct |
5 |
Correct |
1 ms |
464 KB |
Output is correct |
6 |
Correct |
1 ms |
464 KB |
Output is correct |
7 |
Correct |
2 ms |
464 KB |
Output is correct |
8 |
Correct |
0 ms |
208 KB |
Output is correct |
9 |
Correct |
1 ms |
208 KB |
Output is correct |
10 |
Correct |
1 ms |
208 KB |
Output is correct |
11 |
Correct |
1 ms |
208 KB |
Output is correct |
12 |
Correct |
0 ms |
208 KB |
Output is correct |
13 |
Correct |
1 ms |
208 KB |
Output is correct |
14 |
Correct |
1 ms |
208 KB |
Output is correct |
15 |
Correct |
2 ms |
336 KB |
Output is correct |
16 |
Correct |
3 ms |
464 KB |
Output is correct |
17 |
Correct |
2 ms |
464 KB |
Output is correct |
18 |
Correct |
1 ms |
208 KB |
Output is correct |
19 |
Correct |
1 ms |
208 KB |
Output is correct |
20 |
Correct |
3 ms |
336 KB |
Output is correct |
21 |
Correct |
2 ms |
464 KB |
Output is correct |
22 |
Correct |
2 ms |
464 KB |
Output is correct |
23 |
Correct |
0 ms |
208 KB |
Output is correct |
24 |
Correct |
1 ms |
208 KB |
Output is correct |
25 |
Correct |
1 ms |
336 KB |
Output is correct |
26 |
Incorrect |
2 ms |
336 KB |
1st lines differ - on the 1st token, expected: '153', found: '423' |
27 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
2 ms |
336 KB |
Output is correct |
3 |
Correct |
2 ms |
336 KB |
Output is correct |
4 |
Correct |
2 ms |
464 KB |
Output is correct |
5 |
Correct |
1 ms |
464 KB |
Output is correct |
6 |
Correct |
1 ms |
464 KB |
Output is correct |
7 |
Correct |
2 ms |
464 KB |
Output is correct |
8 |
Correct |
0 ms |
208 KB |
Output is correct |
9 |
Correct |
1 ms |
208 KB |
Output is correct |
10 |
Correct |
1 ms |
208 KB |
Output is correct |
11 |
Correct |
1 ms |
208 KB |
Output is correct |
12 |
Correct |
0 ms |
208 KB |
Output is correct |
13 |
Correct |
1 ms |
208 KB |
Output is correct |
14 |
Correct |
1 ms |
208 KB |
Output is correct |
15 |
Correct |
2 ms |
336 KB |
Output is correct |
16 |
Correct |
3 ms |
464 KB |
Output is correct |
17 |
Correct |
2 ms |
464 KB |
Output is correct |
18 |
Correct |
1 ms |
208 KB |
Output is correct |
19 |
Correct |
1 ms |
208 KB |
Output is correct |
20 |
Correct |
3 ms |
336 KB |
Output is correct |
21 |
Correct |
2 ms |
464 KB |
Output is correct |
22 |
Correct |
2 ms |
464 KB |
Output is correct |
23 |
Correct |
0 ms |
208 KB |
Output is correct |
24 |
Correct |
1 ms |
208 KB |
Output is correct |
25 |
Correct |
1 ms |
336 KB |
Output is correct |
26 |
Incorrect |
2 ms |
336 KB |
1st lines differ - on the 1st token, expected: '153', found: '423' |
27 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4003 ms |
7668 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
308 ms |
2060 KB |
3rd lines differ - on the 1st token, expected: '150', found: '1550' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
2 ms |
336 KB |
Output is correct |
3 |
Correct |
2 ms |
336 KB |
Output is correct |
4 |
Correct |
2 ms |
464 KB |
Output is correct |
5 |
Correct |
1 ms |
464 KB |
Output is correct |
6 |
Correct |
1 ms |
464 KB |
Output is correct |
7 |
Correct |
2 ms |
464 KB |
Output is correct |
8 |
Correct |
0 ms |
208 KB |
Output is correct |
9 |
Correct |
1 ms |
208 KB |
Output is correct |
10 |
Correct |
1 ms |
208 KB |
Output is correct |
11 |
Correct |
1 ms |
208 KB |
Output is correct |
12 |
Correct |
0 ms |
208 KB |
Output is correct |
13 |
Correct |
1 ms |
208 KB |
Output is correct |
14 |
Correct |
1 ms |
208 KB |
Output is correct |
15 |
Correct |
2 ms |
336 KB |
Output is correct |
16 |
Correct |
3 ms |
464 KB |
Output is correct |
17 |
Correct |
2 ms |
464 KB |
Output is correct |
18 |
Correct |
1 ms |
208 KB |
Output is correct |
19 |
Correct |
1 ms |
208 KB |
Output is correct |
20 |
Correct |
3 ms |
336 KB |
Output is correct |
21 |
Correct |
2 ms |
464 KB |
Output is correct |
22 |
Correct |
2 ms |
464 KB |
Output is correct |
23 |
Correct |
0 ms |
208 KB |
Output is correct |
24 |
Correct |
1 ms |
208 KB |
Output is correct |
25 |
Correct |
1 ms |
336 KB |
Output is correct |
26 |
Incorrect |
2 ms |
336 KB |
1st lines differ - on the 1st token, expected: '153', found: '423' |
27 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
350 ms |
988 KB |
Output is correct |
2 |
Correct |
906 ms |
1576 KB |
Output is correct |
3 |
Correct |
847 ms |
1352 KB |
Output is correct |
4 |
Correct |
664 ms |
1360 KB |
Output is correct |
5 |
Correct |
889 ms |
1448 KB |
Output is correct |
6 |
Correct |
749 ms |
1352 KB |
Output is correct |
7 |
Correct |
845 ms |
1436 KB |
Output is correct |
8 |
Correct |
1 ms |
208 KB |
Output is correct |
9 |
Correct |
1 ms |
208 KB |
Output is correct |
10 |
Correct |
1 ms |
208 KB |
Output is correct |
11 |
Correct |
1 ms |
336 KB |
Output is correct |
12 |
Correct |
2 ms |
336 KB |
Output is correct |
13 |
Correct |
2 ms |
336 KB |
Output is correct |
14 |
Correct |
2 ms |
464 KB |
Output is correct |
15 |
Correct |
1 ms |
464 KB |
Output is correct |
16 |
Correct |
1 ms |
464 KB |
Output is correct |
17 |
Correct |
2 ms |
464 KB |
Output is correct |
18 |
Correct |
0 ms |
208 KB |
Output is correct |
19 |
Correct |
1 ms |
208 KB |
Output is correct |
20 |
Correct |
1 ms |
208 KB |
Output is correct |
21 |
Correct |
1 ms |
208 KB |
Output is correct |
22 |
Correct |
0 ms |
208 KB |
Output is correct |
23 |
Correct |
1 ms |
208 KB |
Output is correct |
24 |
Correct |
1 ms |
208 KB |
Output is correct |
25 |
Correct |
2 ms |
336 KB |
Output is correct |
26 |
Correct |
3 ms |
464 KB |
Output is correct |
27 |
Correct |
2 ms |
464 KB |
Output is correct |
28 |
Correct |
1 ms |
208 KB |
Output is correct |
29 |
Correct |
1 ms |
208 KB |
Output is correct |
30 |
Correct |
3 ms |
336 KB |
Output is correct |
31 |
Correct |
2 ms |
464 KB |
Output is correct |
32 |
Correct |
2 ms |
464 KB |
Output is correct |
33 |
Correct |
0 ms |
208 KB |
Output is correct |
34 |
Correct |
1 ms |
208 KB |
Output is correct |
35 |
Correct |
1 ms |
336 KB |
Output is correct |
36 |
Incorrect |
2 ms |
336 KB |
1st lines differ - on the 1st token, expected: '153', found: '423' |
37 |
Halted |
0 ms |
0 KB |
- |