oj.uz

Submission #89284

# Submission time Handle Problem Language Result Execution time Memory
89284 2018-12-11T10:36:50 Z theknife2001 Bob (COCI14_bob) C++17
72 / 120
 1000 ms 66560 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 18552 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 28592 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 29848 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 30972 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 32124 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 42384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1057 ms 51776 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1048 ms 61832 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1047 ms 66560 KB Time limit exceeded
2 Halted 0 ms 0 KB -