oj.uz

Submission #965207

# Submission time Handle Problem Language Result Execution time Memory
965207 2024-04-18T08:16:09 Z phoenix0423 Cell Automaton (JOI23_cell) C++17
24 / 100
 580 ms 255532 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 <= 1000){
        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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 126288 KB Output is correct
2 Correct 483 ms 126096 KB Output is correct
3 Correct 503 ms 126276 KB Output is correct
4 Correct 413 ms 126192 KB Output is correct
5 Correct 466 ms 126192 KB Output is correct
6 Correct 428 ms 126368 KB Output is correct
7 Correct 463 ms 126036 KB Output is correct
8 Correct 419 ms 126496 KB Output is correct
9 Correct 445 ms 126196 KB Output is correct
10 Correct 463 ms 125944 KB Output is correct
11 Correct 458 ms 126188 KB Output is correct
12 Correct 464 ms 126236 KB Output is correct
13 Correct 488 ms 126032 KB Output is correct
14 Correct 478 ms 126460 KB Output is correct
15 Correct 469 ms 126232 KB Output is correct
16 Correct 476 ms 126192 KB Output is correct
17 Correct 469 ms 126192 KB Output is correct
18 Correct 539 ms 126100 KB Output is correct
19 Correct 471 ms 126036 KB Output is correct
20 Correct 501 ms 126192 KB Output is correct
21 Correct 464 ms 126036 KB Output is correct
22 Correct 497 ms 126368 KB Output is correct
23 Correct 475 ms 126164 KB Output is correct
24 Correct 503 ms 126036 KB Output is correct
25 Correct 467 ms 126188 KB Output is correct
26 Correct 504 ms 126032 KB Output is correct
27 Correct 500 ms 126192 KB Output is correct
28 Correct 502 ms 126356 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 126288 KB Output is correct
2 Correct 483 ms 126096 KB Output is correct
3 Correct 503 ms 126276 KB Output is correct
4 Correct 413 ms 126192 KB Output is correct
5 Correct 466 ms 126192 KB Output is correct
6 Correct 428 ms 126368 KB Output is correct
7 Correct 463 ms 126036 KB Output is correct
8 Correct 419 ms 126496 KB Output is correct
9 Correct 445 ms 126196 KB Output is correct
10 Correct 463 ms 125944 KB Output is correct
11 Correct 458 ms 126188 KB Output is correct
12 Correct 464 ms 126236 KB Output is correct
13 Correct 488 ms 126032 KB Output is correct
14 Correct 478 ms 126460 KB Output is correct
15 Correct 469 ms 126232 KB Output is correct
16 Correct 476 ms 126192 KB Output is correct
17 Correct 469 ms 126192 KB Output is correct
18 Correct 539 ms 126100 KB Output is correct
19 Correct 471 ms 126036 KB Output is correct
20 Correct 501 ms 126192 KB Output is correct
21 Correct 464 ms 126036 KB Output is correct
22 Correct 497 ms 126368 KB Output is correct
23 Correct 475 ms 126164 KB Output is correct
24 Correct 503 ms 126036 KB Output is correct
25 Correct 467 ms 126188 KB Output is correct
26 Correct 504 ms 126032 KB Output is correct
27 Correct 500 ms 126192 KB Output is correct
28 Correct 502 ms 126356 KB Output is correct
29 Correct 479 ms 126292 KB Output is correct
30 Correct 500 ms 126152 KB Output is correct
31 Correct 521 ms 126208 KB Output is correct
32 Correct 502 ms 134836 KB Output is correct
33 Correct 507 ms 126040 KB Output is correct
34 Correct 493 ms 126288 KB Output is correct
35 Correct 475 ms 126032 KB Output is correct
36 Correct 465 ms 126008 KB Output is correct
37 Correct 504 ms 126192 KB Output is correct
38 Correct 482 ms 126732 KB Output is correct
39 Correct 496 ms 128488 KB Output is correct
40 Correct 580 ms 136516 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 9048 KB Output is correct
2 Correct 43 ms 9816 KB Output is correct
3 Correct 44 ms 8280 KB Output is correct
4 Correct 43 ms 9708 KB Output is correct
5 Correct 44 ms 8268 KB Output is correct
6 Correct 43 ms 8296 KB Output is correct
7 Correct 47 ms 9804 KB Output is correct
8 Correct 487 ms 126680 KB Output is correct
9 Correct 498 ms 126192 KB Output is correct
10 Correct 1 ms 472 KB Output is correct
11 Correct 43 ms 9036 KB Output is correct

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 9048 KB Output is correct
2 Correct 43 ms 9816 KB Output is correct
3 Correct 44 ms 8280 KB Output is correct
4 Correct 43 ms 9708 KB Output is correct
5 Correct 44 ms 8268 KB Output is correct
6 Correct 43 ms 8296 KB Output is correct
7 Correct 47 ms 9804 KB Output is correct
8 Correct 487 ms 126680 KB Output is correct
9 Correct 498 ms 126192 KB Output is correct
10 Correct 1 ms 472 KB Output is correct
11 Correct 43 ms 9036 KB Output is correct
12 Correct 147 ms 25128 KB Output is correct
13 Correct 143 ms 25192 KB Output is correct
14 Correct 137 ms 24960 KB Output is correct
15 Correct 139 ms 25092 KB Output is correct
16 Runtime error 573 ms 255532 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 988 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 988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 126288 KB Output is correct
2 Correct 483 ms 126096 KB Output is correct
3 Correct 503 ms 126276 KB Output is correct
4 Correct 413 ms 126192 KB Output is correct
5 Correct 466 ms 126192 KB Output is correct
6 Correct 428 ms 126368 KB Output is correct
7 Correct 463 ms 126036 KB Output is correct
8 Correct 419 ms 126496 KB Output is correct
9 Correct 445 ms 126196 KB Output is correct
10 Correct 463 ms 125944 KB Output is correct
11 Correct 458 ms 126188 KB Output is correct
12 Correct 464 ms 126236 KB Output is correct
13 Correct 488 ms 126032 KB Output is correct
14 Correct 478 ms 126460 KB Output is correct
15 Correct 469 ms 126232 KB Output is correct
16 Correct 476 ms 126192 KB Output is correct
17 Correct 469 ms 126192 KB Output is correct
18 Correct 539 ms 126100 KB Output is correct
19 Correct 471 ms 126036 KB Output is correct
20 Correct 501 ms 126192 KB Output is correct
21 Correct 464 ms 126036 KB Output is correct
22 Correct 497 ms 126368 KB Output is correct
23 Correct 475 ms 126164 KB Output is correct
24 Correct 503 ms 126036 KB Output is correct
25 Correct 467 ms 126188 KB Output is correct
26 Correct 504 ms 126032 KB Output is correct
27 Correct 500 ms 126192 KB Output is correct
28 Correct 502 ms 126356 KB Output is correct
29 Correct 479 ms 126292 KB Output is correct
30 Correct 500 ms 126152 KB Output is correct
31 Correct 521 ms 126208 KB Output is correct
32 Correct 502 ms 134836 KB Output is correct
33 Correct 507 ms 126040 KB Output is correct
34 Correct 493 ms 126288 KB Output is correct
35 Correct 475 ms 126032 KB Output is correct
36 Correct 465 ms 126008 KB Output is correct
37 Correct 504 ms 126192 KB Output is correct
38 Correct 482 ms 126732 KB Output is correct
39 Correct 496 ms 128488 KB Output is correct
40 Correct 580 ms 136516 KB Output is correct
41 Correct 43 ms 9048 KB Output is correct
42 Correct 43 ms 9816 KB Output is correct
43 Correct 44 ms 8280 KB Output is correct
44 Correct 43 ms 9708 KB Output is correct
45 Correct 44 ms 8268 KB Output is correct
46 Correct 43 ms 8296 KB Output is correct
47 Correct 47 ms 9804 KB Output is correct
48 Correct 487 ms 126680 KB Output is correct
49 Correct 498 ms 126192 KB Output is correct
50 Correct 1 ms 472 KB Output is correct
51 Correct 43 ms 9036 KB Output is correct
52 Correct 147 ms 25128 KB Output is correct
53 Correct 143 ms 25192 KB Output is correct
54 Correct 137 ms 24960 KB Output is correct
55 Correct 139 ms 25092 KB Output is correct
56 Runtime error 573 ms 255532 KB Execution killed with signal 11
57 Halted 0 ms 0 KB -