QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#783251 | #6259. Gluttonous Goop | 353cerega# | AC ✓ | 2ms | 10528kb | C++14 | 2.2kb | 2024-11-26 03:16:25 | 2024-11-26 03:16:26 |
Judging History
answer
//#pragma GCC optimize("Ofast", "unroll-loops", "omit-frame-pointer","inline")
//#pragma GCC option("arch=native","tune=native","no-zero-upper")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define X first
#define Y second
const ll mod = 1000000007;
//const ll mod = 998244353;
ll pew(ll a, ll b) {
ll res = 1;
while (b>0) {
if (b&1) res = res*a%mod;
b >>= 1;
a = a*a%mod;
}
return res;
}
const ll N = 200353;
ll A[N], mx[N], h[N];
vector<ll> g[N];
void dfs(int u) {
mx[u] = h[u];
if (g[u].size()==0) return;
for (int v: g[u]) {
h[v] = h[u]+1;
dfs(v);
if (mx[u]==h[u]) {
mx[u] = mx[v];
continue;
}
if (mx[u]<mx[v]) {
swap(mx[u],mx[v]);
}
A[mx[v]-h[u]]++;
}
}
void solve() {
ll n, m, k;
cin >> n >> m >> k;
vector<string> s(n);
for (ll i=0;i<n;i++) cin >> s[i];
vector<pair<ll,ll>> a;
vector<pair<ll,ll>> ord;
for (ll i=0;i<n;i++) {
for (ll j=0;j<m;j++) {
if (s[i][j]!='#') continue;
ord.push_back({i-k,a.size()});
ord.push_back({i+k+1,a.size()});
a.push_back({j-k,j+k+1});
}
}
sort(ord.begin(),ord.end());
n = a.size();
vector<ll> cur(n);
ll ans = 0;
for (ll w=0;w<ord.size();) {
ll T = ord[w].X;
while (w<ord.size() and ord[w].X==T) {
cur[ord[w].Y] ^= 1;
w++;
}
if (w==ord.size()) break;
ll D = ord[w].X-T;
vector<pair<ll,ll>> q;
for (ll i=0;i<n;i++) {
if (cur[i]==0) continue;
q.push_back({a[i].X,1});
q.push_back({a[i].Y,-1});
}
sort(q.begin(),q.end());
ll Q = 0;
for (ll w=0;w<q.size();w++) {
Q += q[w].Y;
if (Q>0) ans += D*(q[w+1].X-q[w].X);
}
}
cout << ans << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
int T = 1;
//cin >> T;
while (T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9536kb
input:
5 5 3 ..... .###. .#.#. .###. .....
output:
81
result:
ok single line: '81'
Test #2:
score: 0
Accepted
time: 2ms
memory: 10296kb
input:
3 3 1 #.. .#. ..#
output:
19
result:
ok single line: '19'
Test #3:
score: 0
Accepted
time: 2ms
memory: 9304kb
input:
4 6 3 ..##.. .#..#. .#..#. ..##..
output:
96
result:
ok single line: '96'
Test #4:
score: 0
Accepted
time: 0ms
memory: 9436kb
input:
1 1 1000000 #
output:
4000004000001
result:
ok single line: '4000004000001'
Test #5:
score: 0
Accepted
time: 2ms
memory: 9816kb
input:
2 2 91011 .# .#
output:
33132554552
result:
ok single line: '33132554552'
Test #6:
score: 0
Accepted
time: 2ms
memory: 8976kb
input:
20 20 1000000 #################### #################### #################### #################### #################### #################### #################### #################### #################### #################### #################### #################### #################### #############...
output:
4000080000400
result:
ok single line: '4000080000400'
Test #7:
score: 0
Accepted
time: 1ms
memory: 8752kb
input:
20 20 630238 .................... .................... .................... .................... .................... .................... .................... .................... #................... .................... .................... .................... .................... .................
output:
1588840081630
result:
ok single line: '1588840081630'
Test #8:
score: 0
Accepted
time: 2ms
memory: 10528kb
input:
20 20 630238 #................... .#.................. ..#................. ...#................ ....#............... .....#.............. ......#............. .......#............ ........#........... .........#.......... ..........#......... ...........#........ ............#....... .............#...
output:
1588850165636
result:
ok single line: '1588850165636'
Test #9:
score: 0
Accepted
time: 0ms
memory: 8468kb
input:
20 20 1000000 .........##......... ........####........ .......######....... ......########...... .....##########..... ....############.... ...##############... ..################.. .##################. #################### #################### .##################. ..################.. ...##########...
output:
4000080000220
result:
ok single line: '4000080000220'
Test #10:
score: 0
Accepted
time: 1ms
memory: 10084kb
input:
5 5 1000000 ..... ..... ..... ..... .....
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 1ms
memory: 9392kb
input:
5 5 1 ..... ..... ..... ..... .....
output:
0
result:
ok single line: '0'
Test #12:
score: 0
Accepted
time: 0ms
memory: 8640kb
input:
20 20 93002 #################### #..................# #..................# #..................# #..................# #..................# #..................# #..................# #..................# #..................# #..................# #..................# #..................# #.................
output:
34604928576
result:
ok single line: '34604928576'
Test #13:
score: 0
Accepted
time: 0ms
memory: 9024kb
input:
20 20 3 #################### #..................# #..................# #..................# #..................# #..................# #..................# #..................# #..................# #..................# #..................# #..................# #..................# #.....................
output:
532
result:
ok single line: '532'
Test #14:
score: 0
Accepted
time: 1ms
memory: 10160kb
input:
10 12 173312 ...#....##.. ....#.#..... ............ ##.#..#..... ...#...#..#. #..##.....#. #.##.#..#... ....#....#.# .#.#..#..... ............
output:
120155476561
result:
ok single line: '120155476561'
Test #15:
score: 0
Accepted
time: 1ms
memory: 8892kb
input:
16 1 12123 . . # . . . # . . . . . . . . .
output:
588013997
result:
ok single line: '588013997'
Test #16:
score: 0
Accepted
time: 1ms
memory: 8352kb
input:
20 11 78669 ........#.. #.......... ##...#..... .##........ ........... .....#....# ....#...... #.##....... .##...#.#.. ........... ###.#...... ...#...#... .#......... ........... ..........# .........## ..#...#.... ....#.....# ##......... ....###.#..
output:
24760123916
result:
ok single line: '24760123916'
Test #17:
score: 0
Accepted
time: 1ms
memory: 8548kb
input:
3 20 935833 ..#.#.....#...#..... ........#........... .......#............
output:
3503163562228
result:
ok single line: '3503163562228'
Test #18:
score: 0
Accepted
time: 2ms
memory: 9636kb
input:
19 7 528014 ....... .....#. #.#..#. ......# .##...# ..#..#. #..#... ....... .#....# .....#. #...... #...... ......# ..#.... ...#.#. .#..##. ....#.# ###..#. ...#...
output:
1115221537596
result:
ok single line: '1115221537596'
Test #19:
score: 0
Accepted
time: 2ms
memory: 10000kb
input:
15 15 139652 .............#. ............... ............... ............... ............#.. ............... .....#......... .#........#...# ..#............ ..##........... ............... .#............. .#............. ....#.......... ...............
output:
78018544980
result:
ok single line: '78018544980'
Test #20:
score: 0
Accepted
time: 0ms
memory: 9740kb
input:
19 16 10 .#.............. .........#...... ...#............ ................ ....#...#....#.# .............#.. ....#.........#. .........#...... ................ .....#.......... #..............# ......#.......#. .......#........ ........#....#.. .#......#.#.#... #.........#..... ...#..........#. .....
output:
1337
result:
ok single line: '1337'
Test #21:
score: 0
Accepted
time: 2ms
memory: 10152kb
input:
8 19 2 ....#...........#.. ....#.....##....... .............#..... #........###....... ............#...... ........#.....#..#. ..#.....#.......... ...................
output:
195
result:
ok single line: '195'
Test #22:
score: 0
Accepted
time: 1ms
memory: 9148kb
input:
15 1 1 . . . . . . . . . . . . . . .
output:
0
result:
ok single line: '0'
Test #23:
score: 0
Accepted
time: 2ms
memory: 8576kb
input:
18 9 1 ......... ......#.. ........# ......... ......#.. #........ ...#..... .#...#.## ......#.. ........# ..#....#. ......... .......#. #........ .#......# ......... ......... .........
output:
111
result:
ok single line: '111'
Test #24:
score: 0
Accepted
time: 1ms
memory: 10148kb
input:
19 13 4 .........#... ........#.... ..........### .......##...# .........#... ............. ............. ..#.......... ............. ............. ............. .......#..... ............. ..#...#...... ............. ............. .....##...... ............. ....#........
output:
374
result:
ok single line: '374'
Test #25:
score: 0
Accepted
time: 1ms
memory: 10504kb
input:
1 1 1000000 #
output:
4000004000001
result:
ok single line: '4000004000001'
Test #26:
score: 0
Accepted
time: 1ms
memory: 10108kb
input:
1 1 329048 .
output:
0
result:
ok single line: '0'
Test #27:
score: 0
Accepted
time: 1ms
memory: 8504kb
input:
20 20 12890 #..................# .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... ..................
output:
665639639
result:
ok single line: '665639639'
Test #28:
score: 0
Accepted
time: 1ms
memory: 9132kb
input:
2 2 3901 .# ##
output:
60902415
result:
ok single line: '60902415'
Test #29:
score: 0
Accepted
time: 1ms
memory: 8392kb
input:
20 20 630238 #................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................
output:
1588850165294
result:
ok single line: '1588850165294'
Test #30:
score: 0
Accepted
time: 1ms
memory: 8584kb
input:
20 20 630238 #..................# .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................
output:
1588826216592
result:
ok single line: '1588826216592'
Test #31:
score: 0
Accepted
time: 1ms
memory: 9092kb
input:
20 20 630238 ...................# .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................
output:
1588850165294
result:
ok single line: '1588850165294'
Test #32:
score: 0
Accepted
time: 0ms
memory: 10124kb
input:
8 8 2 ........ ........ .....#.. ...##... ...#.... ........ ........ ........
output:
44
result:
ok single line: '44'
Test #33:
score: 0
Accepted
time: 0ms
memory: 10328kb
input:
20 20 0 #################### ##.################# #########..###.##### #########.#####.#### ##.######.#.##.##### ######.##.##.####### #############.###### ######.#######.##### ##########.###..#### #####.##.#####.##### #############.###### #####.###.##.####### #################### ##.##.####.....####...
output:
357
result:
ok single line: '357'