Submission #89363

#	Time	Username	Problem	Language	Result	Execution time	Memory
89363		theknife2001	Bob (COCI14_bob)	C++17	120 / 120	841 ms	48692 KiB

bob

#include <bits/stdc++.h>
#define ll long long
#define mid (l+r)/2
#define ii pair < int , int >
#define fi first
#define se second

using namespace std;
const int N=1055;
int a[N][N];
ii 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].fi=lazy[node][j]*(r-l+1);
    tree[node][j].se=lazy[node][j];
    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].fi=tree[node*2][j].fi+tree[node*2+1][j].fi;
    tree[node][j].se=max(tree[node*2][j].se,tree[node*2+1][j].se);

}

int 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].fi;
    return query(l,mid,node*2,x,y,j)+query(mid+1,r,node*2+1,x,y,j);

}

int sch(int l , int r , int node , int val , int j)
{
    propa(l,r,node,j);
//    cout<<l<<' '<<r<<' '<<val<<' '<<tree[node][j].se<<endl;
    if(l==r)
        return l;
    propa(l,mid,node*2,j);
//    cout<<l<<' '<<mid<<' '<<val<<' '<<tree[node*2][j].se<<endl;
    if(tree[node*2][j].se>=val)
        return sch(l,mid,node*2,val,j);
    else
        return sch(mid+1,r,node*2+1,val,j);
}


void bs(int i , int j , int c)
{
//    cout<<i<<' '<<j<<endl;
    int l=sch(0,n-1,1,c,j);
    update(0,n-1,1,l,i,c,j);
    ans+=query(0,n-1,1,0,i,j);
}

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;
}
/*
5 5
1 2 3 4 5
5 2 2 1 4
1 3 5 9 7
2 1 2 1 2
3 4 3 5 6
*/

• 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: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12