oj.uz

Submission #89362

# Submission time Handle Problem Language Result Execution time Memory
89362 2018-12-12T09:50:12 Z theknife2001 Bob (COCI14_bob) C++17
84 / 120
 852 ms 65992 KB 
#include <bits/stdc++.h>
#define ll long long
#define mid (l+r)/2
#define ii pair < long long , 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);

}

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].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

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18424 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18564 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 32364 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 33416 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 34504 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 35896 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 824 ms 59964 KB Output is correct
2 Correct 760 ms 61848 KB Output is correct
3 Correct 742 ms 63932 KB Output is correct

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 63932 KB Output is correct
2 Runtime error 757 ms 65992 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 852 ms 65992 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 843 ms 65992 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -