Submission #814720

#	Time	Username	Problem	Language	Result	Execution time	Memory
814720		tranxuanbach	Cell Automaton (JOI23_cell)	C++17	32 / 100	585 ms	66996 KiB

cell

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

const int N = 1e5 + 5, Q = 5e5 + 5;

struct point{
    int x, y;
};

int n, q;
point a[N];
int b[Q];

namespace subtask12{
    bool check(){
        ForE(i, 1, n){
            if (not (abs(a[i].x) <= 1000 and abs(a[i].y) <= 1000)){
                return false;
            }
        }
        ForE(i, 1, q){
            if (not (b[i] <= 1000)){
                return false;
            }
        }
        return true;
    }
 
    const int N = 4e3 + 5, offset = 2e3;
 
    int dist[N][N];
    int ans[N];
 
    vpii dir = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
 
    void solve(){
        For(x, 0, N){
            For(y, 0, N){
                dist[x][y] = -1;
            }
        }
        queue <pii> qu;
        ForE(i, 1, n){
            a[i].x += offset; a[i].y += offset;
            dist[a[i].x][a[i].y] = 0;
            qu.emplace(a[i].x, a[i].y);
        }
        while (not qu.empty()){
            auto [x, y] = qu.front(); qu.pop();
            ans[dist[x][y]]++;
            if (dist[x][y] == N - 1){
                break;
            }
            for (auto [dx, dy]: dir){
                int tx = x + dx, ty = y + dy;
                if (0 <= tx and tx < N and 0 <= ty and ty < N and dist[tx][ty] == -1){
                    dist[tx][ty] = dist[x][y] + 1;
                    qu.emplace(tx, ty);
                }
            }
        }
        ForE(i, 1, q){
            cout << ans[b[i]] << "\n";
        }
    }
}

namespace subtask34{
    bool check(){
        ForE(i, 1, n){
            if (not (a[i].x == a[i].y)){
                return false;
            }
        }
        return true;
    }

    vector <int> dif;
    vector <ll> suffdif;

    ll count_dist(int t){
        if (t < 0){
            return 0ll;
        }
        int idx = upper_bound(bend(dif), t) - dif.begin();
        int cnt = isz(dif) - idx;
        ll area = (2ll * a[n].x + t) - (2ll * a[1].x - t) + 1;
        area -= (idx != isz(dif) ? suffdif[idx] : 0ll) * 2;
        area += (2 * t + 1) * cnt;
        area *= (2 * t + 1);
        return (area - (cnt + 1)) / 2 + (cnt + 1);
    }

    void solve(){
        sort(a + 1, a + n + 1, [&](const point& p, const point& q){
            return p.x < q.x;
        });
        ForE(i, 2, n){
            dif.emplace_back(a[i].x - a[i - 1].x);
        }
        sort(bend(dif));
        suffdif = vector <ll>(bend(dif));
        FordE(i, isz(suffdif) - 2, 0){
            suffdif[i] += suffdif[i + 1];
        }
        ForE(i, 1, q){
            ll ans = count_dist(b[i]) - count_dist(b[i] - 1);
            cout << ans << "\n";
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    cin >> n >> q;
    ForE(i, 1, n){
        cin >> a[i].x >> a[i].y;
    }
    ForE(i, 1, q){
        cin >> b[i];
    }

    if (subtask12::check()){
        subtask12::solve();
        return 0;
    }
    if (subtask34::check()){
        subtask34::solve();
        return 0;
    }
}

/*
==================================================+
INPUT                                             |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 26