oj.uz

Submission #1045921

# Submission time Handle Problem Language Result Execution time Memory
1045921 2024-08-06T08:32:33 Z 정민찬(#11016) Cell Automaton (JOI23_cell) C++17
17 / 100
 8000 ms 19052 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

ll solve(vector<pll> a, ll T) {
    ll N = a.size();
    vector<array<ll,3>> upd;
    for (ll i=0; i<N; i++) {
        upd.push_back({a[i].first - T, a[i].second - T, 1});
        upd.push_back({a[i].first + T + 1, a[i].second - T, -1});
        //printf("*%d %d %d\n", a[i].first - T, a[i].first + T + 1, a[i].first);
    }
    sort(upd.begin(), upd.end());
    vector<ll> v;
    ll ans = 0;
    for (ll i=0; i<upd.size(); i++) {
        if (i + 1 == upd.size()) break;
        if (upd[i][2] == 1) {
            v.push_back(upd[i][1]);
            sort(v.begin(), v.end());
        }
        else {
            for (ll j=0; j<v.size(); j++) {
                if (v[j] == upd[i][1]) {
                    v.erase(v.begin() + j);
                    break;
                }
            }
        }
        if (upd[i+1][0] == upd[i][0]) continue;
        if (v.empty()) continue;
        //printf("%d %d\n", upd[i][0], upd[i+1][0]);
        vector<ll> cnt(2, 0);
        ll p = v[0];
        for (ll j=1; j<v.size(); j++) {
            if (v[j-1] + 2*T < v[j]) {
                cnt[0] += (v[j-1] + 2*T - p + 1) / 2;
                cnt[1] += (v[j-1] + 2*T - p + 1) / 2;
                if (abs(v[j-1]) % 2 == abs(p) % 2) {
                    cnt[abs(p) % 2] ++;
                }
                p = v[j];
            }
        }
        cnt[0] += (v.back() + 2*T - p + 1) / 2;
        cnt[1] += (v.back() + 2*T - p + 1) / 2;
        if (abs(v.back()) % 2 == abs(p) % 2) {
            cnt[abs(p) % 2] ++;
        }
        vector<ll> cnt2(2, 0);
        ll l = upd[i][0], r = upd[i+1][0] - 1;
        cnt2[0] = cnt2[1] = (r - l + 1) / 2;
        if (abs(r) % 2 == abs(l) % 2) {
            cnt2[abs(l) % 2] ++;
        }
        ans += cnt[0] * cnt2[0] + cnt[1] * cnt2[1];
        //printf("\n");
        //printf("%d %d %d %d\n", cnt[0], cnt[1], cnt2[0], cnt2[1]);
    }
    return ans;
}

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    ll N, Q;
    cin >> N >> Q;
    vector<pll> a;
    for (ll i=0; i<N; i++) {
        ll x, y;
        cin >> x >> y;
        a.push_back({x+y, x-y});
        //printf("%d %d\n", x+y, x-y);
    }
    //cout << solve(a, 1) << '\n';
    while (Q --) {
        ll t;
        cin >> t;
        if (t == 0) {
            cout << N << '\n';
        }
        else {
            cout << solve(a, t) - solve(a, t-1) << '\n';
        }
    }
}

Compilation message

cell.cpp: In function 'll solve(std::vector<std::pair<long long int, long long int> >, ll)':
cell.cpp:19:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (ll i=0; i<upd.size(); i++) {
      |                  ~^~~~~~~~~~~
cell.cpp:20:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         if (i + 1 == upd.size()) break;
      |             ~~~~~~^~~~~~~~~~~~~
cell.cpp:26:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |             for (ll j=0; j<v.size(); j++) {
      |                          ~^~~~~~~~~
cell.cpp:38:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for (ll j=1; j<v.size(); j++) {
      |                      ~^~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Execution timed out 8019 ms 2232 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Execution timed out 8019 ms 2232 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 17832 KB Output is correct
2 Correct 60 ms 17924 KB Output is correct
3 Correct 58 ms 18060 KB Output is correct
4 Correct 59 ms 17776 KB Output is correct
5 Correct 67 ms 17664 KB Output is correct
6 Correct 59 ms 18288 KB Output is correct
7 Correct 58 ms 19052 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Execution timed out 8089 ms 13584 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 17832 KB Output is correct
2 Correct 60 ms 17924 KB Output is correct
3 Correct 58 ms 18060 KB Output is correct
4 Correct 59 ms 17776 KB Output is correct
5 Correct 67 ms 17664 KB Output is correct
6 Correct 59 ms 18288 KB Output is correct
7 Correct 58 ms 19052 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Execution timed out 8089 ms 13584 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 752 KB Output is correct
2 Correct 55 ms 604 KB Output is correct
3 Correct 23 ms 764 KB Output is correct
4 Correct 46 ms 604 KB Output is correct

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 752 KB Output is correct
2 Correct 55 ms 604 KB Output is correct
3 Correct 23 ms 764 KB Output is correct
4 Correct 46 ms 604 KB Output is correct
5 Execution timed out 8044 ms 852 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Execution timed out 8019 ms 2232 KB Time limit exceeded
9 Halted 0 ms 0 KB -