#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=2e3+5;
char grid[nax][nax];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int arx[4]={1,-1,0,0};
int ary[4]={0,0,1,-1};
pair<int,int> segtree[4*nax];
int lazy[nax*4];
bool vis[nax][nax];
vector<bool> v(nax);
struct point{
int idx,l,r,sum;
};
vector<point> tab[nax];
void build(int pos,int l,int r){
if(l==r){
segtree[pos]={0,l};
return;
}
int mid=(r+l)/2;
build(pos*2+1,l,mid);
build(pos*2+2,mid+1,r);
segtree[pos]=max(segtree[pos*2+1],segtree[pos*2+2]);
return;
}
void propagate(int pos){
if(lazy[pos]!=0){
lazy[pos*2+1]+=lazy[pos];
lazy[pos*2+2]+=lazy[pos];
segtree[pos*2+1].fi+=lazy[pos];
segtree[pos*2+2].fi+=lazy[pos];
}
lazy[pos]=0;
}
void update(int pos,int l,int r,int left,int right,int value){
if(l>r||l>right||r<left) return;
if(l>=left&&r<=right){
segtree[pos].fi+=value;
lazy[pos]+=value;
return;
}
int mid=(r+l)/2;
propagate(pos);
update(pos*2+1,l,mid,left,right,value);
update(pos*2+2,mid+1,r,left,right,value);
segtree[pos]=max(segtree[pos*2+1],segtree[pos*2+2]);
return;
}
int n,m;
bool safe(int x,int y){
return x>=0&&y>=0&&x<n&&y<m&&!vis[x][y]&&grid[x][y]!='.';
}
int mx,mn;
int cur=0;
void dfs(int x,int y){
vis[x][y]=true;
mn=min(mn,y);
mx=max(mx,y);
cur+=(grid[x][y]-'0');
for (int i = 0; i < 4; ++i)
{
int nex=x+arx[i];
int ney=y+ary[i];
if(safe(nex,ney)){
dfs(nex,ney);
}
}
}
int main(){
cin>>n>>m;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
cin>>grid[i][j];
}
}
int cnt=0;
build(0,0,m-1);
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if(vis[i][j]||grid[i][j]=='.') continue;
mn=j;
mx=j;
cur=0;
dfs(i,j);
update(0,0,m-1,mn,mx,cur);
for (int k = mn; k <= mx; ++k)
{
tab[k].pb({cnt,mn,mx,cur});
}
cnt++;
}
}
int ans=0;
for (int i = 0; i < m; ++i)
{
auto cur=segtree[0];
ans+=cur.fi;
for (int j = 0; j < tab[cur.se].size(); ++j)
{
//cout << tab[cur.se][j].idx<<" "<<tab[cur.se][j].l<<" "<<tab[cur.se][j].r<<" "<<tab[cur.se][j].sum<<endl;
if(v[tab[cur.se][j].idx]) continue;
v[tab[cur.se][j].idx]=true;
update(0,0,m-1,tab[cur.se][j].l,tab[cur.se][j].r,-tab[cur.se][j].sum);
}
cout <<ans<<endl;
}
}
Compilation message
nafta.cpp: In function 'int main()':
nafta.cpp:108:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for (int j = 0; j < tab[cur.se].size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
