oj.uz

Submission #475660

# Submission time Handle Problem Language Result Execution time Memory
475660 2021-09-23T15:22:13 Z cpp219 Strah (COCI18_strah) C++14
110 / 110
 132 ms 4204 KB 
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
typedef pair<ld,ll> LD;
const ll N = 2e3 + 9;
const ll mod = 1e9 + 7;
const ll base = 31;

ll n,m,ans,h[N],lf[N],rg[N];
string s;

ll cal(ll x){
    return x * (x + 1)/2;
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n>>m;
    for (ll i = 1;i <= n;i++){
        cin>>s; s = " " + s; vector<ll> st;
        for (ll j = 1;j <= m;j++){
            if (s[j] == '.') h[j]++;
            else h[j] = 0;
        }
        for (ll j = 1;j <= m;j++){
            while(!st.empty() && h[st.back()] >= h[j]) st.pop_back();
            if (!st.empty()) lf[j] = st.back();
            else lf[j] = 0; st.push_back(j);
        }
        st.clear();
        for (ll j = m;j > 0;j--){
            while(!st.empty() && h[st.back()] > h[j]) st.pop_back();
            if (!st.empty()) rg[j] = st.back();
            else rg[j] = m + 1; st.push_back(j);
        }
        for (ll j = 1;j <= m;j++){
            ll r = rg[j] - j,l = j - lf[j];
            ll tmp = r * cal(l) + l * cal(r) - l*r;
            ans += tmp * cal(h[j]);
            //cout<<lf[j]<<" "<<rg[j]<<"\n";
        }
    }
    cout<<ans;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message

strah.cpp: In function 'int main()':
strah.cpp:38:13: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   38 |             else lf[j] = 0; st.push_back(j);
      |             ^~~~
strah.cpp:38:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   38 |             else lf[j] = 0; st.push_back(j);
      |                             ^~
strah.cpp:44:13: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   44 |             else rg[j] = m + 1; st.push_back(j);
      |             ^~~~
strah.cpp:44:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   44 |             else rg[j] = m + 1; st.push_back(j);
      |                                 ^~
strah.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 3 ms 428 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 420 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1360 KB Output is correct
2 Correct 85 ms 2652 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 2764 KB Output is correct
2 Correct 122 ms 3936 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 1872 KB Output is correct
2 Correct 82 ms 2892 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 588 KB Output is correct
2 Correct 74 ms 3176 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 4204 KB Output is correct
2 Correct 132 ms 4180 KB Output is correct