Submission #1001340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001340		MarwenElarbi	Nafta (COI15_nafta)	C++17	0 / 100	1 ms	2648 KiB

nafta

#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 (stderr)

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)
      |                         ~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 66