Submission #257890

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
257890	2020-08-05T02:21:13 Z	leductoan	Bob (COCI14_bob)	C++14	120 / 120	153 ms	25868 KB

#include<bits/stdc++.h>

using namespace std;

#define task "bhouse"
#define fi first
#define se second

template <typename T>
inline void read(T& x)
{
   bool Neg = false;
   char c;
   for (c = getchar(); c < '0' | c > '9'; c = getchar())
       if (c == '-') Neg = !Neg;
   x = c - '0';
   for (c = getchar(); c >= '0' && c <= '9'; c = getchar())
       x = x * 10 + c - '0';
   if (Neg) x = -x;
}

template <typename T>
inline void write(T x)
{
   if (x < 0)
   {
       putchar('-'); x = -x;
   }
   T p = 1;
   for (T temp = x / 10; temp > 0; temp /= 10) p *= 10;
   for (; p > 0; x %= p, p /= 10) putchar(x / p + '0');
}

typedef long double ld;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;

const int mxn=1005;
int n,m,a[mxn][mxn],p[mxn][mxn],h[mxn];
ll ans=0,f[mxn][mxn];
void solve()
{
    read(n); read(m);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
//            cin>>a[i][j];
            read(a[i][j]);
            if(a[i][j]!=a[i][j-1]) p[i][j]=j;
            else p[i][j]=p[i][j-1];
        }
    }

    for(int i=1;i<=n;++i)
    {
        deque<int> q;
        for(int j=1;j<=m;++j)
        {
            if(a[i][j]==a[i-1][j]) ++h[j];
            else h[j]=1;
            while(!q.empty()&&a[i][j]!=a[i][q.front()]) q.pop_front();
            while(!q.empty()&&h[q.back()]>=h[j]) q.pop_back();
            int pos=0;
            if(!q.empty()) pos=q.back();
            else pos=p[i][j]-1;
//            if(i==3&&j==3) cout<<h[j]<<' '<<pos<<'\n';
            if(a[i][j]==a[i][pos]) f[i][j]=f[i][pos]+(j-pos)*h[j];
            else f[i][j]=(j-pos)*h[j];
            ans+=f[i][j];
            q.push_back(j);
        }
    }
//    cout<<f[3][3]<<'\n';
    cout<<ans;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    solve();
}

Compilation message

bob.cpp: In instantiation of 'void read(T&) [with T = int]':
bob.cpp:44:11:   required from here
bob.cpp:14:26: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
    for (c = getchar(); c < '0' | c > '9'; c = getchar())
                        ~~^~~~~
bob.cpp: In function 'int main()':
bob.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(task".inp","r",stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bob.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(task".out","w",stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

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

Subtask #7
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	107 ms	22776 KB	Output is correct
2	Correct	39 ms	18040 KB	Output is correct
3	Correct	39 ms	18044 KB	Output is correct

Subtask #8
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	153 ms	25868 KB	Output is correct
2	Correct	46 ms	18040 KB	Output is correct
3	Correct	37 ms	17964 KB	Output is correct

Subtask #9
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	145 ms	25688 KB	Output is correct
2	Correct	45 ms	18040 KB	Output is correct
3	Correct	37 ms	18040 KB	Output is correct

Subtask #10
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	147 ms	25848 KB	Output is correct
2	Correct	50 ms	17984 KB	Output is correct
3	Correct	37 ms	18040 KB	Output is correct