oj.uz

답안 #89363

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
89363 2018-12-12T09:51:32 Z theknife2001 Bob (COCI14_bob) C++17
120 / 120
 841 ms 48692 KB 
#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.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 18424 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 18560 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 27792 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 193 ms 27900 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 194 ms 27920 KB Output is correct

Subtask #6
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 190 ms 27940 KB Output is correct

Subtask #7
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 781 ms 38804 KB Output is correct
2 Correct 745 ms 38812 KB Output is correct
3 Correct 722 ms 38816 KB Output is correct

Subtask #8
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 820 ms 38868 KB Output is correct
2 Correct 761 ms 38876 KB Output is correct
3 Correct 729 ms 40688 KB Output is correct

Subtask #9
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 841 ms 40728 KB Output is correct
2 Correct 741 ms 42832 KB Output is correct
3 Correct 743 ms 44600 KB Output is correct

Subtask #10
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 825 ms 44720 KB Output is correct
2 Correct 830 ms 46648 KB Output is correct
3 Correct 734 ms 48692 KB Output is correct