Submission #555475

#	Time	Username	Problem	Language	Result	Execution time	Memory
555475		gg123_pe	Bob (COCI14_bob)	C++14	120 / 120	156 ms	13980 KiB

bob

#include <bits/stdc++.h>
using namespace std; 

typedef long long ll; 
#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)

const int N = 1005; 

ll ans, res[N]; 
int n, m, A[N][N], a[N], st[N][10]; 

int mini(int l, int r){
    int log = 31 - __builtin_clz(r-l+1); 
    return min(st[l][log], st[r-(1<<log)+1][log]); 
}
void solve(int x, int y){
    res[y+1] = 0; 
    fa(i,y,x){
        int l = i, r = y; 
        while(l < r){
            int mid = (l+r+1)>>1; 
            if(mini(i,mid) == a[i]) l = mid; 
            else r = mid-1; 
        }
        res[i] = (ll) a[i] * (ll) (l-i+1) + res[l+1]; 
        ans += res[i]; 
    }
}
int main(){
    scanf("%d %d", &n, &m); 

    f(i,1,n+1) f(j,1,m+1) scanf("%d", &A[i][j]); 
    
    f(j,1,m+1){
        f(i,1,n+1){
            if(A[i][j-1] == A[i][j]) a[i]++; 
            else a[i] = 1; 
            st[i][0] = a[i]; 
        }
        f(k,1,10){
            f(i,1,n+1){
                int x = i + (1<<(k-1)); 
                if(x > n) break;
                st[i][k] = min(st[i][k-1], st[x][k-1]);
            }
        }
        int id = 1; 
        while(id <= n){
            int l = id, comp = A[id][j], r; 
            while(id <= n and A[id][j] == comp) id++; 
            r = id-1; 

            solve(l, r); 
        }
    }
    printf("%lld\n", ans);
    return 0; 
}

Compilation message (stderr)

bob.cpp: In function 'int main()':
bob.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bob.cpp:33:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     f(i,1,n+1) f(j,1,m+1) scanf("%d", &A[i][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: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12