Submission #965194

#	Time	Username	Problem	Language	Result	Execution time	Memory
965194		phoenix0423	Cell Automaton (JOI23_cell)	C++17	24 / 100	606 ms	255860 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){
    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(int i = 0; i < q; i++){
        int t;
        cin>>t;
        cout<<ans[t]<<"\n";
    }
    return;
}

signed main(void){
    fastio;
    cin>>n>>q;
    int mx = 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});
    }
    if(mx <= 1000){
        sol1(e);
        return 0;
    }
    sort(e.begin(), e.end());
    vector<int> dist;
    for(int i = 1; i < n; i++) dist.pb(e[i].f - e[i - 1].f);
    sort(dist.begin(), dist.end());
    int id = 0;
    int comp = n, face = n * 4, ans = n;
    int prv = 0;
    vector<pll> op;
    for(auto x : dist) op.pb({x, -1}), op.pb({x, 2});
    for(int i = 0; i < q; i++){
        int x;
        cin>>x;
        op.pb({x, 1});
    }
    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";
    }


}

Compilation message (stderr)

cell.cpp: In function 'int main()':
cell.cpp:70:9: warning: unused variable 'id' [-Wunused-variable]
   70 |     int id = 0;
      |         ^~
cell.cpp:71:9: warning: unused variable 'comp' [-Wunused-variable]
   71 |     int comp = n, face = n * 4, ans = n;
      |         ^~~~

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