oj.uz

답안 #713756

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
713756 2023-03-23T02:28:43 Z ALTAKEXE Bob (COCI14_bob) C++14
120 / 120
 181 ms 17232 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
typedef pair <int,int> ii;
const int N = 1e3 + 9;
const int oo = 1e10;
int n,m,a[N][N],high[N][N],l[N],r[N],res = 0;
void solve(int a[],int h[],bool kt)
{
    stack <int> s;
    h[0] = -oo;
    s.push(0);
    for (int i = 1;i <= m;i++)
      {
        while (h[i] < h[s.top()] && a[i] == a[s.top()]) s.pop();
        l[i] = s.top() + 1;
        s.push(i);
      }
    while (s.size()) s.pop();
    s.push(m + 1);
    h[m + 1] = -oo;
    for (int i = m;i >= 1;i--)
      {
        while (h[i] <= h[s.top()] && a[i] == a[s.top()]) s.pop();
        r[i] = s.top() - 1;
        s.push(i);
      }
    int lim_r;
    int tmp = res;
    for (int i = 1;i <= m;i++)
      {
        if (kt) tmp = res;
        tmp = res;
        res += (i - l[i] + 1) * (r[i] - i + 1);
        if (a[r[i] + 1] != a[i] || r[i] == m) lim_r = 1;
        else lim_r = h[r[i] + 1] + 1;
        // if (kt && i == m) cout<< res - tmp<<endl;
        res += (h[i] - lim_r) * (i - l[i] + 1) * (r[i] - i + 1) + (lim_r - 1) * (i - l[i] + 1) * (r[i] - i + 1);
        // if (kt) cout<<lim_r<<" ";
        // if (kt) cout<<res - tmp<<endl;
      }  
    // cout<<res - tmp<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // freopen("test.inp","r",stdin);
    // freopen("check1.out","w",stdout);
    cin>>n>>m;
    for (int i = 1;i <= n;i++)
      for (int j = 1;j <= m;j++)
        cin>>a[i][j];
    for (int i = 1;i <= n;i++)
      for (int j = 1;j <= m;j++)
        if (a[i][j] != a[i-1][j]) high[i][j] = 1;
        else high[i][j] = high[i-1][j] + 1;
    for (int i = 1;i <= n;i++)
      solve(a[i],high[i],(i == 2));
    cout<<res;
    return 0;
}

Compilation message

bob.cpp: In function 'void solve(long long int*, long long int*, bool)':
bob.cpp:29:9: warning: variable 'tmp' set but not used [-Wunused-but-set-variable]
   29 |     int tmp = res;
      |         ^~~

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

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

Subtask #7
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 17204 KB Output is correct
2 Correct 76 ms 17116 KB Output is correct
3 Correct 71 ms 17188 KB Output is correct

Subtask #8
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 181 ms 17224 KB Output is correct
2 Correct 77 ms 17232 KB Output is correct
3 Correct 80 ms 17216 KB Output is correct

Subtask #9
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 17152 KB Output is correct
2 Correct 72 ms 17148 KB Output is correct
3 Correct 69 ms 17212 KB Output is correct

Subtask #10
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 142 ms 17144 KB Output is correct
2 Correct 73 ms 17228 KB Output is correct
3 Correct 87 ms 17184 KB Output is correct