| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 227911 |
2020-04-29T08:37:52 Z |
Vimmer |
Strah (COCI18_strah) |
C++14 |
|
1000 ms |
86276 KB |
#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
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;
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
512 KB |
Output is correct |
| 2 |
Correct |
5 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
6 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
853 ms |
12876 KB |
Output is correct |
| 2 |
Execution timed out |
1082 ms |
6108 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
820 ms |
12920 KB |
Output is correct |
| 2 |
Execution timed out |
1092 ms |
6008 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1095 ms |
86276 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
4736 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
7912 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
5896 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
2944 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
22 ms |
11136 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
