Submission #1002877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002877		MarwenElarbi	Nafta (COI15_nafta)	C++17	34 / 100	1076 ms	27880 KiB

nafta

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#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];
int arx[4]={1,-1,0,0};
int ary[4]={0,0,1,-1};
int segtree[4*nax];
int lazy[nax*4];
bool vis[nax][nax];
vector<int> dp(nax);
vector<bool> v(nax);
struct point{
    int x,type,upd,sum;
    bool operator<(point &o) const{
        if(o.x!=x) return x<o.x;
        else return type<o.type;
    }
};
vector<point> sweep;
void build(int pos,int l,int r){
    lazy[pos]=0;
    if(l==r){
        segtree[pos]=dp[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]+=lazy[pos];
        segtree[pos*2+2]+=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]+=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 query(int pos,int l,int r,int left,int right){
    if(l>r||l>right||r<left) return -1e9;
    if(l>=left&&r<=right) return segtree[pos];
    int mid=(r+l)/2;
    propagate(pos);
    return max(query(pos*2+1,l,mid,left,right),query(pos*2+2,mid+1,r,left,right));
}
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;
    dp.resize(m+1,0);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            cin>>grid[i][j];
        }
    }
    int cnt=0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if(vis[i][j]||grid[i][j]=='.') continue;
            mn=j;
            mx=j;
            cur=0;
            dfs(i,j);
            sweep.pb({mn,0,mn-1,cur});  
            sweep.pb({mx,2,mn-1,cur}); 
        }
    }
    for (int i = 0; i < m; ++i) sweep.pb({i+1,1,-1,0});
    sort(sweep.begin(),sweep.end());
    for (int k = 0; k < m; ++k)
    {
        build(0,0,m);
        //cout <<query(0,0,m,0,0)<<endl;
        int ans=0;
        for (int j = 0; j < sweep.size(); ++j)
        {
            auto cur=sweep[j];
            //cout <<k<<" "<<cur.x<<" "<<cur.type<<" "<<cur.upd<<" "<<cur.sum<<endl;
            //cout <<query(0,0,m,0,0)<<endl;
            if(cur.type==0){
                //cout <<"he"<<endl;
                //cout <<cur.upd<<" "<<cur.sum<<endl;
                update(0,0,m,0,cur.upd,cur.sum);
            }else if(cur.type==1){
                if(cur.x<=k) continue;
                //cout <<query(0,0,m,0,cur.x)<<endl;
                dp[cur.x]=query(0,0,m,0,cur.x-1);
                ans=max(ans,dp[cur.x]);
            }else{
                update(0,0,m,0,cur.upd,-cur.sum);
            }//cout <<query(0,0,m,0,0)<<endl;
        }//cout <<endl;
        /*for (int i = 0; i <= m; ++i)
        {
            cout <<dp[i]<<" ";
        }cout <<endl;*/
        cout <<ans<<endl;
    }
}

Compilation message (stderr)

nafta.cpp: In function 'int main()':
nafta.cpp:120:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         for (int j = 0; j < sweep.size(); ++j)
      |                         ~~^~~~~~~~~~~~~~
nafta.cpp:99:9: warning: unused variable 'cnt' [-Wunused-variable]
   99 |     int cnt=0;
      |         ^~~

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