QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#783251#6259. Gluttonous Goop353cerega#AC ✓2ms10528kbC++142.2kb2024-11-26 03:16:252024-11-26 03:16:26

Judging History

你现在查看的是最新测评结果

  • [2024-11-26 03:16:26]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:10528kb
  • [2024-11-26 03:16:25]
  • 提交

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;
}

详细

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'