Submission #44374

#	Time	Username	Problem	Language	Result	Execution time	Memory
44374		Nnandi	Bob (COCI14_bob)	C++14	120 / 120	277 ms	60288 KiB

bob

#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 / 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