Submission #89284

#	Time	Username	Problem	Language	Result	Execution time	Memory
89284		theknife2001	Bob (COCI14_bob)	C++17	72 / 120	1068 ms	66560 KiB

bob

#include <bits/stdc++.h>
#define ll long long
#define mid (l+r)/2

using namespace std;
const int N=1055;
int a[N][N];
int dp[N][N];
long long tree[N*4][N];
int lazy[N*4][N];
int n,m;
long long ans;


void propa(int l , int r , int node , int j)
{
    if(lazy[node][j]==-1)
        return ;
    if(l!=r)
    {
        lazy[node*2][j]=lazy[node][j];
        lazy[node*2+1][j]=lazy[node][j];
    }
    tree[node][j]=lazy[node][j]*(r-l+1);
    lazy[node][j]=-1;
}

void update(int l , int r , int node , int x , int y , int val , int j)
{
    propa(l,r,node,j);
    if(x>r||l>y||x>y)
        return ;
    if(x<=l&&r<=y)
    {
        lazy[node][j]=val;
        propa(l,r,node,j);
        return ;
    }
    update(l,mid,node*2,x,y,val,j);
    update(1+mid,r,1+node*2,x,y,val,j);
    tree[node][j]=tree[node*2][j]+tree[node*2+1][j];

}

ll query(int l , int r , int node , int x , int y , int j)
{
    propa(l,r,node,j);
    if(x>r||l>y||x>y)
        return 0;
    if(x<=l&&r<=y)
        return tree[node][j];
        int t=query(l,mid,node*2,x,y,j)+query(mid+1,r,node*2+1,x,y,j);
        return t;

}

void bs(int i , int j , int c)
{
    int l=0,r=i;
    while(l<r)
    {
        if(query(0,n-1,1,mid,mid,j)>c)
            r=mid;
        else
            l=mid+1;
    }
    update(0,n-1,1,l,i,c,j);
    int t=query(0,n-1,1,0,i,j);
    ans+=t;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(lazy,-1,sizeof lazy);
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=0;i<n;i++)
    {
        int cnt=1;
        for(int j=0;j<m;j++)
        {
            if(j)
            {
                if(a[i][j-1]==a[i][j])
                    cnt++;
                else
                    cnt=1;
            }
            if(i)
            {
                if(a[i-1][j]!=a[i][j])
                    update(0,n-1,1,0,n-1,0,j);
                update(0,n-1,1,i,i,cnt,j);
                bs(i,j,cnt);
            }
            else
            {
                ans+=cnt;
                update(0,n-1,1,i,i,cnt,j);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

bob.cpp: In function 'long long int query(int, int, int, int, int, int)':
bob.cpp:50:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if(x<=l&&r<=y)
     ^~
bob.cpp:52:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
         int t=query(l,mid,node*2,x,y,j)+query(mid+1,r,node*2+1,x,y,j);
         ^~~

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12