oj.uz

Submission #1002870

# Submission time Handle Problem Language Result Execution time Memory
1002870 2024-06-19T20:55:48 Z MarwenElarbi Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 28328 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];
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);
        for (int i = 0; i < m*4; ++i)
        {
            lazy[i]=0;
        }
        //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:124:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         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 3 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 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 3 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 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 401 ms 2260 KB Output is correct
8 Correct 216 ms 2004 KB Output is correct
9 Correct 35 ms 2968 KB Output is correct
10 Correct 243 ms 2008 KB Output is correct
11 Correct 106 ms 1884 KB Output is correct
12 Correct 31 ms 1628 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 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 401 ms 2260 KB Output is correct
8 Correct 216 ms 2004 KB Output is correct
9 Correct 35 ms 2968 KB Output is correct
10 Correct 243 ms 2008 KB Output is correct
11 Correct 106 ms 1884 KB Output is correct
12 Correct 31 ms 1628 KB Output is correct
13 Execution timed out 1063 ms 28328 KB Time limit exceeded
14 Halted 0 ms 0 KB -