oj.uz

Submission #44374

# Submission time Handle Problem Language Result Execution time Memory
44374 2018-04-01T10:00:10 Z Nnandi Bob (COCI14_bob) C++14
120 / 120
 277 ms 60288 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn=1005;
const int maxs=maxn*maxn;
const int kit=12;
int n, m;

typedef long long ll;
ll sol=0;

int a[maxn][maxn];
int val[maxn], h[maxn];

int tab[kit][maxn];

void init() {
    memset(val,-1,maxn);
    memset(h,0,maxn);
    return;
}

void calc_rmq() {
    for(int k=1;k<kit;k++) {
        for(int j=0;j<m;j++) {
            int elso=tab[k-1][j];
            int maso=min(m-1,tab[k-1][j+(1<<(k-1))]);
            if(h[elso]<h[maso]) {
                tab[k][j]=elso;
            }
            else {
                tab[k][j]=maso;
            }
        }
    }
    return;
}

int get_rmq(int p1, int p2) {
    int k=(int)log2(p2-p1+1);
    int poz1=tab[k][p1];
    int poz2=tab[k][(p2-(1<<k)+1)];
    if(h[poz1]<h[poz2]) {
        return poz1;
    }
    else {
        return poz2;
    }
}

void eval(int from, int to, int exa) {
    if(from>to) return;
    int hol=get_rmq(from,to);
    int l=to-from+1;
    sol+=(ll)(l*(l+1)/2)*(ll)(h[hol]-exa);
    exa=h[hol];
    eval(from,hol-1,exa);
    eval(hol+1,to,exa);
    return;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cin>>a[i][j];
        }
    }
    init();
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(val[j]==a[i][j]) {
                h[j]++;
            }
            else {
                val[j]=a[i][j];
                h[j]=1;
            }
            tab[0][j]=j;
        }
        calc_rmq();
        for(int j=0;j<m;j++) {
            int veg=j;
            while(veg+1<m && val[veg+1]==val[j]) {
                veg++;
            }
            eval(j,veg,0);
            j=veg;
        }
    }
    cout<<sol<<endl;
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

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

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 15348 KB Output is correct
2 Correct 146 ms 17380 KB Output is correct
3 Correct 148 ms 19356 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 28992 KB Output is correct
2 Correct 152 ms 30928 KB Output is correct
3 Correct 153 ms 33012 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 42708 KB Output is correct
2 Correct 155 ms 44760 KB Output is correct
3 Correct 153 ms 46732 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 56336 KB Output is correct
2 Correct 143 ms 58280 KB Output is correct
3 Correct 158 ms 60288 KB Output is correct