#include<bits/stdc++.h>
using namespace std;
pair<int,int>tab[8010];
vector<pair<int,int>>points;
struct kwadrat{pair<int, int> A; pair<int,int>B;};
vector<kwadrat>warstwy[2];
int wynik, n;
pair<int,int>rotate(pair<int,int>A){
int pomx = A.second;
int pomy = n-A.first+1;
return {pomx, pomy};
}
kwadrat rotateK(kwadrat A){
A.A = rotate(A.A);
A.B = rotate(A.B);
swap(A.A.second, A.B.second);
return A;
}
const int base = 1<<13;
const int inf = 1000000;
int tree[2*base];
void dodaj(int x, int w){
x+=base;
while(x>0){
tree[x] = min(tree[x], w);
x/=2;
}
}
int query(int w, int l, int p, int a, int b){
if(l>b || p<a)return inf;
if(a<=l && p<=b)
return tree[w];
return min(query(w*2, l, (l+p)/2, a, b), query(w*2+1, (l+p)/2+1, p, a, b));
}
void policz(int w){
vector<pair<int,int>>vec;
vector<int>pom(n+1,inf);
for(int i = 0;i<(int)warstwy[!w].size();i++)
vec.push_back({warstwy[!w][i].A.first-warstwy[!w][i].A.second, (i+1)});
for(int i=0;i<(int)points.size();i++)
vec.push_back({points[i].first-points[i].second, -(i+1)});
sort(vec.begin(), vec.end());
for(auto &j:tree)j = inf;
for(auto j: vec){
if(j.second<0){
int i = -j.second-1;
int xd = query(1, 0, base-1, points[i].first+1, base-1);
pom[i] = min(pom[i], xd-points[i].second);
// printf(" %d %d %d\n", points[i].first, points[i].second, pom[i]);
}
else{
int i = j.second-1;
dodaj(warstwy[!w][i].A.first, warstwy[!w][i].B.second);
}
}
reverse(vec.begin(), vec.end());
for(auto &j:tree)j = inf;
for(auto j: vec){
if(j.second<0){
int i = -j.second-1;
int xd = query(1, 0, base-1, points[i].second+1, base-1);
pom[i] = min(pom[i], xd-points[i].first);
// printf(" %d %d %d\n", points[i].first, points[i].second, pom[i]);
}
else{
int i = j.second-1;
dodaj(warstwy[!w][i].A.second, warstwy[!w][i].B.first);
}
}
for(int i=0;i<(int)points.size();i++)
if(max(points[i].first, points[i].second)+pom[i]<=n)
warstwy[w].push_back({{points[i].first, points[i].second}, {points[i].first+pom[i], points[i].second+pom[i]}});
// for(int i=0;i<(int)points.size();i++)
// printf("%d %d %d\n", points[i].first, points[i].second, pom[i]);
// for(auto j: warstwy[w])
// printf("%d %d %d %d\n", j.A.first, j.A.second, j.B.first, j.B.second);
// printf("\n");
}
int main()
{
int i, a;
scanf("%d", &n);
for(i=1;i<=n;i++){
scanf("%d", &a);
tab[i].first = i;
tab[i].second = a;
warstwy[0].push_back({{i, a}, {i,a}});
points.push_back({i, a});
}
wynik = 0;
for(int w=1;warstwy[!w].size()>0;w^=1){
wynik++;
// printf("%d\n", wynik);
warstwy[w].clear();
for(i=0;i<4;i++){
policz(w);
for(auto &j: warstwy[!w])
j = rotateK(j);
for(auto &j: warstwy[w])
j = rotateK(j);
for(auto &j: points)
j = rotate(j);
}
// for(auto j: warstwy[w])printf("%d %d %d %d\n", j.A.first, j.A.second, j.B.first, j.B.second);printf("\n");
// exit(0);
}
printf("%d\n", n-wynik);
}
Compilation message
giraffes.cpp: In function 'int main()':
giraffes.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
giraffes.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
93 | scanf("%d", &a);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
444 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
2 ms |
348 KB |
Output is correct |
| 18 |
Correct |
1 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
348 KB |
Output is correct |
| 20 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
444 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
2 ms |
348 KB |
Output is correct |
| 18 |
Correct |
1 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
348 KB |
Output is correct |
| 20 |
Correct |
1 ms |
348 KB |
Output is correct |
| 21 |
Correct |
2 ms |
604 KB |
Output is correct |
| 22 |
Correct |
5 ms |
348 KB |
Output is correct |
| 23 |
Correct |
11 ms |
348 KB |
Output is correct |
| 24 |
Correct |
16 ms |
348 KB |
Output is correct |
| 25 |
Correct |
21 ms |
348 KB |
Output is correct |
| 26 |
Correct |
21 ms |
576 KB |
Output is correct |
| 27 |
Correct |
22 ms |
348 KB |
Output is correct |
| 28 |
Correct |
21 ms |
448 KB |
Output is correct |
| 29 |
Correct |
22 ms |
348 KB |
Output is correct |
| 30 |
Correct |
24 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
444 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
2 ms |
348 KB |
Output is correct |
| 18 |
Correct |
1 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
348 KB |
Output is correct |
| 20 |
Correct |
1 ms |
348 KB |
Output is correct |
| 21 |
Correct |
2 ms |
604 KB |
Output is correct |
| 22 |
Correct |
5 ms |
348 KB |
Output is correct |
| 23 |
Correct |
11 ms |
348 KB |
Output is correct |
| 24 |
Correct |
16 ms |
348 KB |
Output is correct |
| 25 |
Correct |
21 ms |
348 KB |
Output is correct |
| 26 |
Correct |
21 ms |
576 KB |
Output is correct |
| 27 |
Correct |
22 ms |
348 KB |
Output is correct |
| 28 |
Correct |
21 ms |
448 KB |
Output is correct |
| 29 |
Correct |
22 ms |
348 KB |
Output is correct |
| 30 |
Correct |
24 ms |
348 KB |
Output is correct |
| 31 |
Correct |
531 ms |
1240 KB |
Output is correct |
| 32 |
Correct |
2211 ms |
1924 KB |
Output is correct |
| 33 |
Correct |
3683 ms |
2516 KB |
Output is correct |
| 34 |
Correct |
3654 ms |
2516 KB |
Output is correct |
| 35 |
Correct |
3640 ms |
2516 KB |
Output is correct |
| 36 |
Correct |
3720 ms |
2516 KB |
Output is correct |
| 37 |
Correct |
3649 ms |
2524 KB |
Output is correct |
| 38 |
Correct |
3682 ms |
2616 KB |
Output is correct |
| 39 |
Correct |
3643 ms |
2516 KB |
Output is correct |
| 40 |
Correct |
3636 ms |
2516 KB |
Output is correct |
