oj.uz

Submission #863964

# Submission time Handle Problem Language Result Execution time Memory
863964 2023-10-21T15:02:48 Z Danilo21 Cell Automaton (JOI23_cell) C++17
16 / 100
 772 ms 451128 KB 
#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) (__builtin_popcountll(a))
#define bithigh(a) (63-__builtin_clzll(a))
#define lg bithigh
#define highpow(a) (1LL << (ll)lg(a))

using namespace std;

const ll LINF = 4e18;
const int mxN = 1e6+10, A = 5e3+10, INF = 2e9;
int n, m;
array<int, 2> a[mxN];

ll dist[A][A], cnt[2*A];
bool vis[A][A];
array<int, 2> dxdy[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

bool Valid(int i, int j){ return i >= 0 && i < A && j >= 0 && j < A && !vis[i][j]; }

void BF(){

    queue<array<int, 2> > q;
    for (int i = 0; i < n; i++){
        auto [x, y] = a[i];
        x += A/2; y += A/2;
        q.push({x, y});
        vis[x][y] = 1;
        cnt[0]++;
    }
    while (q.size()){
        auto [i, j] = q.front(); q.pop();
        for (auto [dx, dy] : dxdy){
            int x = i+dx, y = j+dy;
            if (Valid(x, y)){
                vis[x][y] = 1;
                dist[x][y] = dist[i][j] + 1;
                cnt[dist[x][y]]++;
                q.push({x, y});
            }
        }
    }
    while (m--){
        ri(t);
        cout << cnt[t] << en;
    }
}

ll b[mxN];
vector<ll> mrg;

void Solve1(){

    for (int i = 0; i < n; i++)
        b[i] = a[i][0];
    sort(b, b+n);
    for (int i = 0; i < n-1; i++)
        mrg.pb(b[i+1] - b[i]);
    sort(all(mrg));
    int k = 0;
    ll N = n, E = 0;
    while (m--){
        ri(t);
        int cnt = 0;
        while (mrg[k] <= t){
            E += mrg[k]-1;
            N--;
            if (mrg[k] == t)
                cnt++;
            k++;
        }

        if (t) cout << 2*(n*(t+1) - (n-N)*t + E) + (2*N + cnt)*(t-1) << en;
        else cout << n << en;
    }
}

void Solve(){

    cin >> n >> m;
    bool f = 0;
    for (int i = 0; i < n; i++){
        cin >> a[i][0] >> a[i][1];
        if (a[i][0] != a[i][1]) f = 0;
    }
    if (f) Solve1();
    else BF();
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); cerr.tie(0);
    cout << setprecision(12) << fixed;
    cerr << setprecision(12) << fixed;
    cerr << "Started!" << endl;

    int t = 1;
    //cin >> t;
    while (t--)
        Solve();

    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 222552 KB Output is correct
2 Correct 633 ms 222480 KB Output is correct
3 Correct 650 ms 222844 KB Output is correct
4 Correct 636 ms 222708 KB Output is correct
5 Correct 616 ms 222660 KB Output is correct
6 Correct 666 ms 222708 KB Output is correct
7 Correct 628 ms 222808 KB Output is correct
8 Correct 659 ms 222780 KB Output is correct
9 Correct 647 ms 222960 KB Output is correct
10 Correct 654 ms 222544 KB Output is correct
11 Correct 695 ms 222544 KB Output is correct
12 Correct 658 ms 222728 KB Output is correct
13 Correct 639 ms 222792 KB Output is correct
14 Correct 634 ms 222716 KB Output is correct
15 Correct 621 ms 222740 KB Output is correct
16 Correct 679 ms 222676 KB Output is correct
17 Correct 635 ms 222480 KB Output is correct
18 Correct 630 ms 222804 KB Output is correct
19 Correct 656 ms 222956 KB Output is correct
20 Correct 632 ms 222912 KB Output is correct
21 Correct 648 ms 222508 KB Output is correct
22 Correct 669 ms 222912 KB Output is correct
23 Correct 661 ms 222708 KB Output is correct
24 Correct 638 ms 222712 KB Output is correct
25 Correct 630 ms 222548 KB Output is correct
26 Correct 675 ms 222624 KB Output is correct
27 Correct 690 ms 222548 KB Output is correct
28 Correct 671 ms 222960 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 222552 KB Output is correct
2 Correct 633 ms 222480 KB Output is correct
3 Correct 650 ms 222844 KB Output is correct
4 Correct 636 ms 222708 KB Output is correct
5 Correct 616 ms 222660 KB Output is correct
6 Correct 666 ms 222708 KB Output is correct
7 Correct 628 ms 222808 KB Output is correct
8 Correct 659 ms 222780 KB Output is correct
9 Correct 647 ms 222960 KB Output is correct
10 Correct 654 ms 222544 KB Output is correct
11 Correct 695 ms 222544 KB Output is correct
12 Correct 658 ms 222728 KB Output is correct
13 Correct 639 ms 222792 KB Output is correct
14 Correct 634 ms 222716 KB Output is correct
15 Correct 621 ms 222740 KB Output is correct
16 Correct 679 ms 222676 KB Output is correct
17 Correct 635 ms 222480 KB Output is correct
18 Correct 630 ms 222804 KB Output is correct
19 Correct 656 ms 222956 KB Output is correct
20 Correct 632 ms 222912 KB Output is correct
21 Correct 648 ms 222508 KB Output is correct
22 Correct 669 ms 222912 KB Output is correct
23 Correct 661 ms 222708 KB Output is correct
24 Correct 638 ms 222712 KB Output is correct
25 Correct 630 ms 222548 KB Output is correct
26 Correct 675 ms 222624 KB Output is correct
27 Correct 690 ms 222548 KB Output is correct
28 Correct 671 ms 222960 KB Output is correct
29 Correct 624 ms 222544 KB Output is correct
30 Correct 621 ms 222716 KB Output is correct
31 Correct 635 ms 222756 KB Output is correct
32 Correct 700 ms 225988 KB Output is correct
33 Correct 619 ms 222800 KB Output is correct
34 Correct 674 ms 222548 KB Output is correct
35 Correct 637 ms 222576 KB Output is correct
36 Correct 659 ms 223120 KB Output is correct
37 Correct 660 ms 222744 KB Output is correct
38 Correct 658 ms 223112 KB Output is correct
39 Correct 683 ms 223724 KB Output is correct
40 Correct 732 ms 226388 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 8796 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 8796 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 772 ms 451128 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 772 ms 451128 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 222552 KB Output is correct
2 Correct 633 ms 222480 KB Output is correct
3 Correct 650 ms 222844 KB Output is correct
4 Correct 636 ms 222708 KB Output is correct
5 Correct 616 ms 222660 KB Output is correct
6 Correct 666 ms 222708 KB Output is correct
7 Correct 628 ms 222808 KB Output is correct
8 Correct 659 ms 222780 KB Output is correct
9 Correct 647 ms 222960 KB Output is correct
10 Correct 654 ms 222544 KB Output is correct
11 Correct 695 ms 222544 KB Output is correct
12 Correct 658 ms 222728 KB Output is correct
13 Correct 639 ms 222792 KB Output is correct
14 Correct 634 ms 222716 KB Output is correct
15 Correct 621 ms 222740 KB Output is correct
16 Correct 679 ms 222676 KB Output is correct
17 Correct 635 ms 222480 KB Output is correct
18 Correct 630 ms 222804 KB Output is correct
19 Correct 656 ms 222956 KB Output is correct
20 Correct 632 ms 222912 KB Output is correct
21 Correct 648 ms 222508 KB Output is correct
22 Correct 669 ms 222912 KB Output is correct
23 Correct 661 ms 222708 KB Output is correct
24 Correct 638 ms 222712 KB Output is correct
25 Correct 630 ms 222548 KB Output is correct
26 Correct 675 ms 222624 KB Output is correct
27 Correct 690 ms 222548 KB Output is correct
28 Correct 671 ms 222960 KB Output is correct
29 Correct 624 ms 222544 KB Output is correct
30 Correct 621 ms 222716 KB Output is correct
31 Correct 635 ms 222756 KB Output is correct
32 Correct 700 ms 225988 KB Output is correct
33 Correct 619 ms 222800 KB Output is correct
34 Correct 674 ms 222548 KB Output is correct
35 Correct 637 ms 222576 KB Output is correct
36 Correct 659 ms 223120 KB Output is correct
37 Correct 660 ms 222744 KB Output is correct
38 Correct 658 ms 223112 KB Output is correct
39 Correct 683 ms 223724 KB Output is correct
40 Correct 732 ms 226388 KB Output is correct
41 Runtime error 23 ms 8796 KB Execution killed with signal 11
42 Halted 0 ms 0 KB -