oj.uz

Submission #81862

# Submission time Handle Problem Language Result Execution time Memory
81862 2018-10-27T12:09:10 Z Shtef Strah (COCI18_strah) C++14
110 / 110
 135 ms 47740 KB 
#include <iostream>
#include <stack>
 
using namespace std;
 
typedef long long ll;
 
int n, m, b[2005][2005], h;
ll val[2005][2005], sol;
 
void initvals(){
    for(ll i = 1 ; i <= m ; ++i){
        val[1][i] = (i * (i + 1) * (i + 2)) / 6LL;
        //cout << val[1][i] << ' ';
    }
    //cout << endl;
    for(ll i = 2 ; i <= n ; ++i){
        for(ll j = 1 ; j <= m ; ++j){
            val[i][j] = val[1][j] * ((i * (i + 1)) / 2LL);
            //cout << val[i][j] << ' ';
        }
        //cout << endl;
    }
}
 
void histval(int a[]){
    stack <int> s;
    int t;
    int i = 0;
    while(i < m){
        if(s.empty() || a[s.top()] <= a[i]){
            s.push(i++);
        }
        else{
            //cout << i << " : " << h << endl;
            t = a[s.top()];
            s.pop();
            if(!s.empty()){
                if(t == a[s.top()])
                    continue;
                /*
                if(!(br[h + 1][i - 1] - br[h + 1][s.top()]))
                    continue;
                if(!t || !(i - s.top() - 1))
                    continue;
                */
                //cout << t << ' ' << i << ' ' << h << ' ' << s.top() << "tu1" << endl;
                sol += val[t][i - s.top() - 1];
                sol -= val[max(a[i], a[s.top()])][i - s.top() - 1];
            }
            else{
                /*
                if(!br[h + 1][i - 1])
                    continue;
                if(!t || !i)
                    continue;
                */
                //cout << t << ' ' << i << ' ' << h << "tu2" << endl;
                sol += val[t][i];
                sol -= val[max(a[i], 0)][i];
            }
        }
    }
    while(!s.empty()){
        t = a[s.top()];
        s.pop();
        if(!s.empty()){
            if(t == a[s.top()])
                continue;
            /*
            if(!(br[h + 1][i - 1] - br[h + 1][s.top()]))
                continue;
            if(!t || !(i - s.top() - 1))
                continue;
            */
            //cout << t << ' ' << i << ' ' << h << ' ' << s.top() << "tu3" << endl;
            sol += val[t][i - s.top() - 1];
            sol -= val[max(a[s.top()], 0)][i - s.top() - 1];
        }
        else{
            /*
            if(!br[h + 1][i - 1])
                continue;
            if(!t || !i)
                continue;
            */
            //cout << t << ' ' << i << ' ' << h << "tu4" << endl;
            sol += val[t][i];
        }
    }
}
 
void getval(){
    histval(b[0]);
    //cout << sol << endl;
    for(int i = 1 ; i < n ; ++i){
        h = i;
        for(int j = 0 ; j < m ; ++j){
            if(b[i][j]){
                b[i][j] += b[i - 1][j];
            }
            //cout << b[i][j] << ' ';
        }
        //cout << endl << endl;
        histval(b[i]);
        //cout << sol << endl;
    }
}
 
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
initvals();
for(int i = 0 ; i < n ; ++i){
    string s;
    cin >> s;
    for(int j = 0 ; j < m ; ++j){
        b[i][j] = (s[j] == '.');
    }
}
getval();
cout << sol << endl;
 
return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3912 KB Output is correct
2 Correct 7 ms 3972 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4048 KB Output is correct
2 Correct 8 ms 4076 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4076 KB Output is correct
2 Correct 7 ms 4104 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 18640 KB Output is correct
2 Correct 78 ms 36204 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 36204 KB Output is correct
2 Correct 115 ms 46188 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 46188 KB Output is correct
2 Correct 84 ms 46188 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 46188 KB Output is correct
2 Correct 84 ms 46188 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 47740 KB Output is correct
2 Correct 135 ms 47740 KB Output is correct