oj.uz

Submission #464691

# Submission time Handle Problem Language Result Execution time Memory
464691 2021-08-13T17:02:10 Z aihay Strah (COCI18_strah) C++14
110 / 110
 136 ms 8516 KB 
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
using namespace std;

typedef int in;
//#define int long long
#define f first
#define s second
#define pb push_back
#define pp push
#define double long double
#define ceil(x,y) (x/y)+(x%y!=0)*((double)(1.0*x/y)<0?0:1)
#define floor(x,y) (x/y)+(x%y!=0)*((double)(1.0a*x/y)<0?-1:0)
const int MAX=1e7;
const int MOD=1e9+7;
const int MAAX=1e18;

int n,m,csum[2010],arr[2010],x,y;
long long ans;
string s[2010];
stack<int> st;

in main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int tc=1;
    //cin>>tc;
    while(tc--){
        cin>>n>>m;
        for(int i=0;i<n;i++){
            cin>>s[i];
            for(int j=0;j<m;j++){
                if(s[i][j]=='.')
                    csum[j]=csum[j]+1;
                else
                    csum[j]=0;
            }
            for(int j=0;j<m;j++){
                while(st.size()&&csum[j]<csum[st.top()]){
                    arr[st.top()]=j-1;
                    st.pop();
                }
                st.pp(j);
            }
            while(st.size()){
                arr[st.top()]=m-1;
                st.pop();
            }
            for(int j=0;j<m;j++){
                x=j,y=arr[j];
                while(x&&csum[x-1]>csum[j]){
                    x--;
                }
                ans+=((y-j+1ll)*(y-j+2ll)/2ll*(j-x+1ll)+(j-x+1ll)*(j-x)/2ll*(y-j+1ll))*((csum[j]*(csum[j]+1ll))/2ll);
            }
        }
        cout<<ans<<endl;
    }
}

Compilation message

strah.cpp:18:16: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   18 | const int MAAX=1e18;
      |                ^~~~

Subtask #1
11.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
11.0 / 11.0

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

Subtask #5
11.0 / 11.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1476 KB Output is correct
2 Correct 89 ms 2824 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 2932 KB Output is correct
2 Correct 122 ms 4292 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1976 KB Output is correct
2 Correct 89 ms 5560 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 636 KB Output is correct
2 Correct 91 ms 3416 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 4484 KB Output is correct
2 Correct 136 ms 8516 KB Output is correct