Submission #227911

#	Time	Username	Problem	Language	Result	Execution time	Memory
227911		Vimmer	Strah (COCI18_strah)	C++14	22 / 110	1095 ms	86276 KiB

strah

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 305
#define M ll(1e9 + 7)

using namespace std;

//using namespace __gnu_pbds;

typedef long double ld;

typedef long long ll;

typedef short int si;

//typedef tree<int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

ll pr[N][N], t[N * 4][N * 4], n, m, psh[N * 4][N * 4];

vector <pair <int, int> > pshr[N * 4];

void Push(int V, int v, int tl, int tr, int l, int r)
{
    if (psh[V][v] == 0) return;

    t[V][v] += ll(r - l + 1) * psh[V][v];

    if (tl != tr)
    {
        psh[V][v + v] += psh[V][v];

        psh[V][v + v + 1] += psh[V][v];
    }

    psh[V][v] = 0;
}
void upd(int V, int v, int tl, int tr, int l, int r, int L, int R)
{
    Push(V, v, tl, tr, L, R);

    if (r < tl || tr < l) return;

    if (l <= tl && tr <= r) {psh[V][v]++; Push(V, v, tl, tr, L, R); return;}

    int md = (tl + tr) >> 1;

    upd(V, v + v, tl, md, l, r, L, R);

    upd(V, v + v + 1, md + 1, tr, l, r, L, R);

    t[V][v] = t[V][v + v] + t[V][v + v + 1];
}

void Pushr(int v, int tl, int tr)
{
    while (sz(pshr[v]) > 0)
    {
        pair <int, int> p = pshr[v].back();

        pshr[v].pop_back();

        upd(v, 1, 0, m - 1, p.F, p.S, tl, tr);

        if (tl != tr)
        {
            pshr[v + v].pb(p);

            pshr[v + v + 1].pb(p);
        }
    }
}
void upd_f(int v, int tl, int tr, int l, int r, int L, int R)
{
    Pushr(v, tl, tr);

    if (tr < l || r < tl) return;

    if (l <= tl && tr <= r) {pshr[v].pb({L, R}); Pushr(v, tl, tr);}

    else
    {
        int md = (tl + tr) >> 1;

        upd_f(v + v, tl, md, l, r, L, R);

        upd_f(v + v + 1, md + 1, tr, l, r, L, R);

        t[v][1] = t[v + v][1] + t[v + v + 1][1];
    }
}

int main()
{
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    string s[n];

    for (int i = 0; i < n; i++) cin >> s[i];

    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
      {
          if (i != 0) pr[i][j] += pr[i - 1][j];

          if (j != 0) pr[i][j] += pr[i][j - 1];

          if (i != 0 && j != 0) pr[i][j] -= pr[i - 1][j - 1];

          if (s[i][j] == '#') pr[i][j]++;
      }

   for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        for (int a = 1; a <= n - i; a++)
          for (int b = 1; b <= m - j; b++)
           {
                int sm = pr[i + a - 1][j + b - 1];

                if (i != 0) sm -= pr[i - 1][j + b - 1];

                if (j != 0) sm -= pr[i + a - 1][j - 1];

                if (i != 0 && j != 0) sm += pr[i - 1][j - 1];

                if (sm != 0) break;

               // cout << i << " " << j << " " << i + a - 1 << " " << j + b - 1 << endl;

                upd_f(1, 0, n - 1, i, i + a - 1, j, j + b - 1);
           }

    cout << t[1][1] << endl;
}

Compilation message (stderr)

strah.cpp: In function 'int main()':
strah.cpp:128:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    for (int i = 0; i < n; i++)
    ^~~
strah.cpp:148:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     cout << t[1][1] << endl;
     ^~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 11
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 11
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11