Submission #965211

#	Time	Username	Problem	Language	Result	Execution time	Memory
965211		phoenix0423	Cell Automaton (JOI23_cell)	C++17	32 / 100	559 ms	136072 KiB

cell

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 4000 + 5;
const int INF = 1e18;
int dist[maxn][maxn];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int n, q;

void sol1(vector<pll> e, vector<pll> op){
    queue<pll> qq;
    for(int i = 0; i < maxn; i++) for(int j = 0; j < maxn; j++) dist[i][j] = INF;
    for(auto [x, y] : e){
        x += maxn / 2, y += maxn / 2;
        dist[x][y] = 0;
        qq.push({x, y});
    }
    vector<int> ans(maxn * 2);
    ans[0] = e.size();
    auto inbound = [&](int x, int y) -> bool {
        return x >= 0 && y >= 0 && x < maxn && y < maxn;
    };
    while(!qq.empty()){
        auto [x, y] = qq.front(); qq.pop();
        for(int d = 0; d < 4; d++){
            int xx = x + dx[d], yy = y + dy[d];
            if(!inbound(xx, yy) || dist[xx][yy] < INF) continue;
            dist[xx][yy] = dist[x][y] + 1;
            ans[dist[xx][yy]] += 1;
            qq.push({xx, yy});
        }
    }
    for(auto [t, tmp] : op){
        cout<<ans[t]<<"\n";
    }
    return;
}

vector<pll> op;
signed main(void){
    fastio;
    cin>>n>>q;
    int mx = 0, mxt = 0;
    vector<pll> e;
    for(int i = 0; i < n; i++){
        int x, y;
        cin>>x>>y;
        mx = max(mx, max(abs(x), abs(y)));
        e.pb({x, y});
    }
    for(int i = 0; i < q; i++){
        int x;
        cin>>x;
        mxt = max(mxt, x);
        op.pb({x, 1});
    }
    if(mx <= 1000 && mxt <= 1000){
        sol1(e, op);
        return 0;
    }
    sort(e.begin(), e.end());
    for(int i = 1; i < n; i++){
        int x = e[i].f - e[i - 1].f;
        op.pb({x, 0}), op.pb({x, 2});
    }
    int face = n * 4, ans = n;
    int prv = 0;
    sort(op.begin(), op.end());
    for(auto [t, val] : op){
        ans += face * (t - prv);
        if(prv == 0 && t != 0) ans -= n;
        prv = t;
        if(val != 1){
            ans -= (t + 1);
            if(val == 2) ans += 2;
            face -= 2;
        }
        else cout<<ans<<"\n";
    }


}

• 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