#include <cstdio>
#ifdef DEBUG
#define D(X) X
#else
#define D(X)
#endif
#include <bits/stdc++.h>
#define F first
#define S second
#define ll long long
#define pi 3.14159265359
#define pub push_back
#define pob pop_back
#define pari pair<int,int>
#define parli pair<long, long>
using namespace std;
const int INF = 1000 * 1000 * 1000;
const ll INF2 = 1LL * 1000 * 1000 * 1000 * 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;
bool comp(vector<ll>& v1, vector<ll>& v2)
{
return v1[0] < v2[0];
}
struct seg {
vector<int> tree;
int sz;
void build(int n) {
sz = 1;
while(sz<n) {
sz *= 2;
}
tree.resize(2*sz + 1, 0);
}
void clean()
{
for(int i=0; i<tree.size(); i++) {
tree[i] = 0;
}
}
void recSet(int idx, int lx, int rx, int i, int val) {
if(rx-lx==1) {
tree[idx] = val;
return;
}
int mid = (lx+rx)/2;
if(i<mid) {
recSet(2*idx+1, lx, mid, i, val);
} else
{
recSet(2*idx+2, mid, rx, i, val);
}
tree[idx] = max(tree[2*idx+1], tree[2*idx+2]);
}
void setX(int i, int val) {
recSet(0, 0, sz, i, val);
}
int rec_range(int idx, int lx, int rx, int l, int r) {
if(lx>=l&&rx<=r) {
return tree[idx];
}
if(rx<=l||lx>=r) return 0;
int mid = (lx+rx)/2;
int left = rec_range(2*idx+1, lx, mid, l, r);
int right = rec_range(2*idx+2, mid, rx, l, r);
return max(left, right);
}
int range(int l, int r) {
return rec_range(0, 0, sz, l, r);
}
};
vector<int> dp;
seg mint, maxt;
map<int, int> ord;
vector<int> h;
int res = 0;
int center = -1;
void init2(int l, int r, int d)
{
int n = h.size();
res = 0;
for(int i=0; i<=n; i++) {
dp[i] = 0;
}
vector<int> used(n+1, 0);
vector<int> nums;
for(int i=l; i<=r; i++) {
int f1 = 0, f2 = 0;
nums.pub(h[i]);
nums.pub(h[i]-d);
nums.pub(h[i]+d);
if(i>l) {
if(h[i]>=h[i-1]) {
f1 = 1;
} else
{
f1 = 2;
}
}
if(i<r) {
if(h[i]>=h[i+1]) {
f2 = 1;
} else
{
f2 = 2;
}
}
if(f1==0) {
f1 = f2;
}
if(f2==0) {
f2 = f1;
}
if(f1==f2) {
used[i] = f1;
}
}
sort(nums.begin(), nums.end());
ord.clear();
ord[nums[0]] = 0;
int sz = nums.size();
for(int i=1; i<sz; i++) {
if(nums[i]>nums[i-1]) {
ord[nums[i]] = ord[nums[i-1]] + 1;
} else
{
ord[nums[i]] = ord[nums[i-1]];
}
}
mint.clean();
maxt.clean();
mint.build(sz);
maxt.build(sz);
for(int i=r; i>=l; i--) {
if(used[i]==0) {
continue;
}
if(used[i]==1&&h[i]-d>0) {
dp[i] = mint.range(0, ord[h[i]-d] + 1);
maxt.setX(ord[h[i]], dp[i]);
}
if(used[i]==2) {
dp[i] = 1 + maxt.range(ord[h[i]+d], sz);
mint.setX(ord[h[i]], dp[i]);
}
res = max(res, dp[i]);
}
}
void init(int n, vector<int> h2)
{
h.resize(n);
for(int i=0; i<n; i++) {
h[i] = h2[i];
}
dp.resize(n+1);
int idx = 1;
while(idx<n&&h[idx]>=h[idx-1]) {
idx++;
}
center = idx - 1;
while(idx<n&&h[idx]<=h[idx-1]) {
idx++;
}
if(idx!=n) {
center = -1;
init2(0, n - 1, 1);
}
}
int max_towers(int l, int r, int d)
{
if(center!=-1) {
if(r<=center||l>=center) {
return 1;
}
if(h[center]-h[l]>=d&&h[center]-h[r]>=d) {
return 2;
}
return 1;
}
init2(l, r, d);
if(l==0&&r==h.size()-1) {
return res;
}
return res;
}
/*
4 0 3 20
0 1 2
1 2 3
18 1 19
*/
/*
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//D(freopen("input.txt","r",stdin);)
//D(freopen("ouput.txt","w",stdout);)
int t = 1;
//cin >> t;
loop:
while(t--)
{
int n;
cin >> n;
vector<int> a(n);
for(int i=0; i<n; i++) {
cin >> a[i];
}
init(n, a);
int res = max_towers(1, 5, 10);
if(res==0) {
res = 1;
}
cout << res;
}
return 0;
}
*/
Compilation message
towers.cpp: In member function 'void seg::clean()':
towers.cpp:43:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i=0; i<tree.size(); i++) {
| ~^~~~~~~~~~~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:199:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
199 | if(l==0&&r==h.size()-1) {
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
259 ms |
1188 KB |
Output is correct |
2 |
Correct |
534 ms |
1860 KB |
Output is correct |
3 |
Correct |
546 ms |
1856 KB |
Output is correct |
4 |
Correct |
525 ms |
2032 KB |
Output is correct |
5 |
Correct |
544 ms |
1860 KB |
Output is correct |
6 |
Correct |
538 ms |
1880 KB |
Output is correct |
7 |
Correct |
560 ms |
1880 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
3 ms |
1164 KB |
Output is correct |
3 |
Correct |
3 ms |
856 KB |
Output is correct |
4 |
Correct |
3 ms |
1064 KB |
Output is correct |
5 |
Correct |
3 ms |
904 KB |
Output is correct |
6 |
Correct |
3 ms |
856 KB |
Output is correct |
7 |
Correct |
3 ms |
856 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
856 KB |
Output is correct |
11 |
Correct |
1 ms |
1108 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
2 ms |
804 KB |
Output is correct |
16 |
Correct |
3 ms |
856 KB |
Output is correct |
17 |
Correct |
3 ms |
856 KB |
Output is correct |
18 |
Correct |
0 ms |
344 KB |
Output is correct |
19 |
Correct |
2 ms |
856 KB |
Output is correct |
20 |
Correct |
3 ms |
856 KB |
Output is correct |
21 |
Correct |
4 ms |
856 KB |
Output is correct |
22 |
Correct |
4 ms |
852 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
2 ms |
856 KB |
Output is correct |
25 |
Correct |
1 ms |
600 KB |
Output is correct |
26 |
Correct |
3 ms |
856 KB |
Output is correct |
27 |
Correct |
3 ms |
932 KB |
Output is correct |
28 |
Correct |
4 ms |
1112 KB |
Output is correct |
29 |
Correct |
4 ms |
856 KB |
Output is correct |
30 |
Correct |
5 ms |
932 KB |
Output is correct |
31 |
Correct |
3 ms |
856 KB |
Output is correct |
32 |
Correct |
1 ms |
344 KB |
Output is correct |
33 |
Correct |
1 ms |
344 KB |
Output is correct |
34 |
Correct |
2 ms |
856 KB |
Output is correct |
35 |
Correct |
2 ms |
856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
3 ms |
1164 KB |
Output is correct |
3 |
Correct |
3 ms |
856 KB |
Output is correct |
4 |
Correct |
3 ms |
1064 KB |
Output is correct |
5 |
Correct |
3 ms |
904 KB |
Output is correct |
6 |
Correct |
3 ms |
856 KB |
Output is correct |
7 |
Correct |
3 ms |
856 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
856 KB |
Output is correct |
11 |
Correct |
1 ms |
1108 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
2 ms |
804 KB |
Output is correct |
16 |
Correct |
3 ms |
856 KB |
Output is correct |
17 |
Correct |
3 ms |
856 KB |
Output is correct |
18 |
Correct |
0 ms |
344 KB |
Output is correct |
19 |
Correct |
2 ms |
856 KB |
Output is correct |
20 |
Correct |
3 ms |
856 KB |
Output is correct |
21 |
Correct |
4 ms |
856 KB |
Output is correct |
22 |
Correct |
4 ms |
852 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
2 ms |
856 KB |
Output is correct |
25 |
Correct |
1 ms |
600 KB |
Output is correct |
26 |
Correct |
3 ms |
856 KB |
Output is correct |
27 |
Correct |
3 ms |
932 KB |
Output is correct |
28 |
Correct |
4 ms |
1112 KB |
Output is correct |
29 |
Correct |
4 ms |
856 KB |
Output is correct |
30 |
Correct |
5 ms |
932 KB |
Output is correct |
31 |
Correct |
3 ms |
856 KB |
Output is correct |
32 |
Correct |
1 ms |
344 KB |
Output is correct |
33 |
Correct |
1 ms |
344 KB |
Output is correct |
34 |
Correct |
2 ms |
856 KB |
Output is correct |
35 |
Correct |
2 ms |
856 KB |
Output is correct |
36 |
Correct |
127 ms |
15656 KB |
Output is correct |
37 |
Correct |
221 ms |
25940 KB |
Output is correct |
38 |
Correct |
183 ms |
25948 KB |
Output is correct |
39 |
Correct |
240 ms |
25756 KB |
Output is correct |
40 |
Correct |
228 ms |
25724 KB |
Output is correct |
41 |
Correct |
328 ms |
26140 KB |
Output is correct |
42 |
Correct |
207 ms |
26048 KB |
Output is correct |
43 |
Correct |
13 ms |
1856 KB |
Output is correct |
44 |
Correct |
9 ms |
1860 KB |
Output is correct |
45 |
Correct |
106 ms |
25796 KB |
Output is correct |
46 |
Correct |
88 ms |
25748 KB |
Output is correct |
47 |
Correct |
204 ms |
25872 KB |
Output is correct |
48 |
Correct |
211 ms |
25700 KB |
Output is correct |
49 |
Correct |
198 ms |
25704 KB |
Output is correct |
50 |
Correct |
9 ms |
1852 KB |
Output is correct |
51 |
Correct |
110 ms |
25792 KB |
Output is correct |
52 |
Correct |
313 ms |
27328 KB |
Output is correct |
53 |
Correct |
362 ms |
27612 KB |
Output is correct |
54 |
Correct |
378 ms |
27380 KB |
Output is correct |
55 |
Correct |
8 ms |
1860 KB |
Output is correct |
56 |
Correct |
163 ms |
28676 KB |
Output is correct |
57 |
Correct |
308 ms |
26920 KB |
Output is correct |
58 |
Correct |
333 ms |
27532 KB |
Output is correct |
59 |
Correct |
334 ms |
27392 KB |
Output is correct |
60 |
Correct |
398 ms |
27748 KB |
Output is correct |
61 |
Correct |
401 ms |
27492 KB |
Output is correct |
62 |
Correct |
387 ms |
27532 KB |
Output is correct |
63 |
Correct |
379 ms |
28404 KB |
Output is correct |
64 |
Correct |
9 ms |
1856 KB |
Output is correct |
65 |
Correct |
9 ms |
1856 KB |
Output is correct |
66 |
Correct |
167 ms |
27472 KB |
Output is correct |
67 |
Correct |
164 ms |
27504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4077 ms |
26252 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4032 ms |
7684 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
3 ms |
1164 KB |
Output is correct |
3 |
Correct |
3 ms |
856 KB |
Output is correct |
4 |
Correct |
3 ms |
1064 KB |
Output is correct |
5 |
Correct |
3 ms |
904 KB |
Output is correct |
6 |
Correct |
3 ms |
856 KB |
Output is correct |
7 |
Correct |
3 ms |
856 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
856 KB |
Output is correct |
11 |
Correct |
1 ms |
1108 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
2 ms |
804 KB |
Output is correct |
16 |
Correct |
3 ms |
856 KB |
Output is correct |
17 |
Correct |
3 ms |
856 KB |
Output is correct |
18 |
Correct |
0 ms |
344 KB |
Output is correct |
19 |
Correct |
2 ms |
856 KB |
Output is correct |
20 |
Correct |
3 ms |
856 KB |
Output is correct |
21 |
Correct |
4 ms |
856 KB |
Output is correct |
22 |
Correct |
4 ms |
852 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
2 ms |
856 KB |
Output is correct |
25 |
Correct |
1 ms |
600 KB |
Output is correct |
26 |
Correct |
3 ms |
856 KB |
Output is correct |
27 |
Correct |
3 ms |
932 KB |
Output is correct |
28 |
Correct |
4 ms |
1112 KB |
Output is correct |
29 |
Correct |
4 ms |
856 KB |
Output is correct |
30 |
Correct |
5 ms |
932 KB |
Output is correct |
31 |
Correct |
3 ms |
856 KB |
Output is correct |
32 |
Correct |
1 ms |
344 KB |
Output is correct |
33 |
Correct |
1 ms |
344 KB |
Output is correct |
34 |
Correct |
2 ms |
856 KB |
Output is correct |
35 |
Correct |
2 ms |
856 KB |
Output is correct |
36 |
Correct |
127 ms |
15656 KB |
Output is correct |
37 |
Correct |
221 ms |
25940 KB |
Output is correct |
38 |
Correct |
183 ms |
25948 KB |
Output is correct |
39 |
Correct |
240 ms |
25756 KB |
Output is correct |
40 |
Correct |
228 ms |
25724 KB |
Output is correct |
41 |
Correct |
328 ms |
26140 KB |
Output is correct |
42 |
Correct |
207 ms |
26048 KB |
Output is correct |
43 |
Correct |
13 ms |
1856 KB |
Output is correct |
44 |
Correct |
9 ms |
1860 KB |
Output is correct |
45 |
Correct |
106 ms |
25796 KB |
Output is correct |
46 |
Correct |
88 ms |
25748 KB |
Output is correct |
47 |
Correct |
204 ms |
25872 KB |
Output is correct |
48 |
Correct |
211 ms |
25700 KB |
Output is correct |
49 |
Correct |
198 ms |
25704 KB |
Output is correct |
50 |
Correct |
9 ms |
1852 KB |
Output is correct |
51 |
Correct |
110 ms |
25792 KB |
Output is correct |
52 |
Correct |
313 ms |
27328 KB |
Output is correct |
53 |
Correct |
362 ms |
27612 KB |
Output is correct |
54 |
Correct |
378 ms |
27380 KB |
Output is correct |
55 |
Correct |
8 ms |
1860 KB |
Output is correct |
56 |
Correct |
163 ms |
28676 KB |
Output is correct |
57 |
Correct |
308 ms |
26920 KB |
Output is correct |
58 |
Correct |
333 ms |
27532 KB |
Output is correct |
59 |
Correct |
334 ms |
27392 KB |
Output is correct |
60 |
Correct |
398 ms |
27748 KB |
Output is correct |
61 |
Correct |
401 ms |
27492 KB |
Output is correct |
62 |
Correct |
387 ms |
27532 KB |
Output is correct |
63 |
Correct |
379 ms |
28404 KB |
Output is correct |
64 |
Correct |
9 ms |
1856 KB |
Output is correct |
65 |
Correct |
9 ms |
1856 KB |
Output is correct |
66 |
Correct |
167 ms |
27472 KB |
Output is correct |
67 |
Correct |
164 ms |
27504 KB |
Output is correct |
68 |
Execution timed out |
4077 ms |
26252 KB |
Time limit exceeded |
69 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
259 ms |
1188 KB |
Output is correct |
2 |
Correct |
534 ms |
1860 KB |
Output is correct |
3 |
Correct |
546 ms |
1856 KB |
Output is correct |
4 |
Correct |
525 ms |
2032 KB |
Output is correct |
5 |
Correct |
544 ms |
1860 KB |
Output is correct |
6 |
Correct |
538 ms |
1880 KB |
Output is correct |
7 |
Correct |
560 ms |
1880 KB |
Output is correct |
8 |
Correct |
0 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
3 ms |
1164 KB |
Output is correct |
13 |
Correct |
3 ms |
856 KB |
Output is correct |
14 |
Correct |
3 ms |
1064 KB |
Output is correct |
15 |
Correct |
3 ms |
904 KB |
Output is correct |
16 |
Correct |
3 ms |
856 KB |
Output is correct |
17 |
Correct |
3 ms |
856 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
0 ms |
344 KB |
Output is correct |
20 |
Correct |
1 ms |
856 KB |
Output is correct |
21 |
Correct |
1 ms |
1108 KB |
Output is correct |
22 |
Correct |
0 ms |
344 KB |
Output is correct |
23 |
Correct |
1 ms |
596 KB |
Output is correct |
24 |
Correct |
0 ms |
344 KB |
Output is correct |
25 |
Correct |
2 ms |
804 KB |
Output is correct |
26 |
Correct |
3 ms |
856 KB |
Output is correct |
27 |
Correct |
3 ms |
856 KB |
Output is correct |
28 |
Correct |
0 ms |
344 KB |
Output is correct |
29 |
Correct |
2 ms |
856 KB |
Output is correct |
30 |
Correct |
3 ms |
856 KB |
Output is correct |
31 |
Correct |
4 ms |
856 KB |
Output is correct |
32 |
Correct |
4 ms |
852 KB |
Output is correct |
33 |
Correct |
1 ms |
344 KB |
Output is correct |
34 |
Correct |
2 ms |
856 KB |
Output is correct |
35 |
Correct |
1 ms |
600 KB |
Output is correct |
36 |
Correct |
3 ms |
856 KB |
Output is correct |
37 |
Correct |
3 ms |
932 KB |
Output is correct |
38 |
Correct |
4 ms |
1112 KB |
Output is correct |
39 |
Correct |
4 ms |
856 KB |
Output is correct |
40 |
Correct |
5 ms |
932 KB |
Output is correct |
41 |
Correct |
3 ms |
856 KB |
Output is correct |
42 |
Correct |
1 ms |
344 KB |
Output is correct |
43 |
Correct |
1 ms |
344 KB |
Output is correct |
44 |
Correct |
2 ms |
856 KB |
Output is correct |
45 |
Correct |
2 ms |
856 KB |
Output is correct |
46 |
Correct |
127 ms |
15656 KB |
Output is correct |
47 |
Correct |
221 ms |
25940 KB |
Output is correct |
48 |
Correct |
183 ms |
25948 KB |
Output is correct |
49 |
Correct |
240 ms |
25756 KB |
Output is correct |
50 |
Correct |
228 ms |
25724 KB |
Output is correct |
51 |
Correct |
328 ms |
26140 KB |
Output is correct |
52 |
Correct |
207 ms |
26048 KB |
Output is correct |
53 |
Correct |
13 ms |
1856 KB |
Output is correct |
54 |
Correct |
9 ms |
1860 KB |
Output is correct |
55 |
Correct |
106 ms |
25796 KB |
Output is correct |
56 |
Correct |
88 ms |
25748 KB |
Output is correct |
57 |
Correct |
204 ms |
25872 KB |
Output is correct |
58 |
Correct |
211 ms |
25700 KB |
Output is correct |
59 |
Correct |
198 ms |
25704 KB |
Output is correct |
60 |
Correct |
9 ms |
1852 KB |
Output is correct |
61 |
Correct |
110 ms |
25792 KB |
Output is correct |
62 |
Correct |
313 ms |
27328 KB |
Output is correct |
63 |
Correct |
362 ms |
27612 KB |
Output is correct |
64 |
Correct |
378 ms |
27380 KB |
Output is correct |
65 |
Correct |
8 ms |
1860 KB |
Output is correct |
66 |
Correct |
163 ms |
28676 KB |
Output is correct |
67 |
Correct |
308 ms |
26920 KB |
Output is correct |
68 |
Correct |
333 ms |
27532 KB |
Output is correct |
69 |
Correct |
334 ms |
27392 KB |
Output is correct |
70 |
Correct |
398 ms |
27748 KB |
Output is correct |
71 |
Correct |
401 ms |
27492 KB |
Output is correct |
72 |
Correct |
387 ms |
27532 KB |
Output is correct |
73 |
Correct |
379 ms |
28404 KB |
Output is correct |
74 |
Correct |
9 ms |
1856 KB |
Output is correct |
75 |
Correct |
9 ms |
1856 KB |
Output is correct |
76 |
Correct |
167 ms |
27472 KB |
Output is correct |
77 |
Correct |
164 ms |
27504 KB |
Output is correct |
78 |
Execution timed out |
4077 ms |
26252 KB |
Time limit exceeded |
79 |
Halted |
0 ms |
0 KB |
- |