oj.uz

Submission #965204

# Submission time Handle Problem Language Result Execution time Memory
965204 2024-04-18T08:15:51 Z phoenix0423 Cell Automaton (JOI23_cell) C++17
16 / 100
 136 ms 25472 KB 
#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;
}

vector<pll> op;
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 < 0){
        sol1(e);
        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;
    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";
    }


}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 8268 KB Output is correct
2 Correct 45 ms 8132 KB Output is correct
3 Correct 44 ms 8296 KB Output is correct
4 Correct 45 ms 8316 KB Output is correct
5 Correct 44 ms 8096 KB Output is correct
6 Correct 48 ms 8272 KB Output is correct
7 Correct 47 ms 8080 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 44 ms 8272 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 8268 KB Output is correct
2 Correct 45 ms 8132 KB Output is correct
3 Correct 44 ms 8296 KB Output is correct
4 Correct 45 ms 8316 KB Output is correct
5 Correct 44 ms 8096 KB Output is correct
6 Correct 48 ms 8272 KB Output is correct
7 Correct 47 ms 8080 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 44 ms 8272 KB Output is correct
12 Correct 131 ms 25156 KB Output is correct
13 Correct 132 ms 25088 KB Output is correct
14 Correct 134 ms 24904 KB Output is correct
15 Correct 136 ms 24912 KB Output is correct
16 Correct 71 ms 15436 KB Output is correct
17 Correct 79 ms 15328 KB Output is correct
18 Correct 94 ms 18616 KB Output is correct
19 Correct 126 ms 25472 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -