oj.uz

Submission #1002877

# Submission time Handle Problem Language Result Execution time Memory
1002877 2024-06-19T20:59:21 Z MarwenElarbi Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 27880 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 2 ms 600 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 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 345 ms 2008 KB Output is correct
8 Correct 235 ms 2008 KB Output is correct
9 Correct 25 ms 2956 KB Output is correct
10 Correct 267 ms 2004 KB Output is correct
11 Correct 72 ms 1884 KB Output is correct
12 Correct 27 ms 1628 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 345 ms 2008 KB Output is correct
8 Correct 235 ms 2008 KB Output is correct
9 Correct 25 ms 2956 KB Output is correct
10 Correct 267 ms 2004 KB Output is correct
11 Correct 72 ms 1884 KB Output is correct
12 Correct 27 ms 1628 KB Output is correct
13 Execution timed out 1076 ms 27880 KB Time limit exceeded
14 Halted 0 ms 0 KB -