oj.uz

Submission #1002863

# Submission time Handle Problem Language Result Execution time Memory
1002863 2024-06-19T20:53:54 Z MarwenElarbi Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 28492 KB 
#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};
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){
    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);
        memset(lazy,0,sizeof lazy);
        //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

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 393 ms 2256 KB Output is correct
8 Correct 216 ms 2004 KB Output is correct
9 Correct 30 ms 2904 KB Output is correct
10 Correct 299 ms 2004 KB Output is correct
11 Correct 76 ms 1880 KB Output is correct
12 Correct 28 ms 1624 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 393 ms 2256 KB Output is correct
8 Correct 216 ms 2004 KB Output is correct
9 Correct 30 ms 2904 KB Output is correct
10 Correct 299 ms 2004 KB Output is correct
11 Correct 76 ms 1880 KB Output is correct
12 Correct 28 ms 1624 KB Output is correct
13 Execution timed out 1012 ms 28492 KB Time limit exceeded
14 Halted 0 ms 0 KB -