oj.uz

Submission #555475

# Submission time Handle Problem Language Result Execution time Memory
555475 2022-05-01T04:19:16 Z gg123_pe Bob (COCI14_bob) C++14
120 / 120
 156 ms 13980 KB 
#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

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

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2812 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3240 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3452 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3404 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 10932 KB Output is correct
2 Correct 131 ms 6156 KB Output is correct
3 Correct 122 ms 6184 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 13980 KB Output is correct
2 Correct 123 ms 6232 KB Output is correct
3 Correct 135 ms 6220 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 13724 KB Output is correct
2 Correct 111 ms 6176 KB Output is correct
3 Correct 112 ms 6200 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 13852 KB Output is correct
2 Correct 127 ms 6228 KB Output is correct
3 Correct 109 ms 6112 KB Output is correct