Submission #965194

#TimeUsernameProblemLanguageResultExecution timeMemory
965194phoenix0423Cell Automaton (JOI23_cell)C++17
24 / 100
606 ms255860 KiB
#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;
      |         ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...