제출 #814716

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
814716		tranxuanbach	Cell Automaton (JOI23_cell)	C++17	16 / 100	146 ms	9900 KiB

cell

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

const int N = 1e5 + 5, Q = 5e5 + 5;

struct point{
    int x, y;
};

int n, q;
point a[N];
int b[Q];

namespace subtask34{
    bool check(){
        ForE(i, 1, n){
            if (not (a[i].x == a[i].y)){
                return false;
            }
        }
        return true;
    }

    vector <int> dif;
    vector <ll> suffdif;

    ll count_dist(int t){
        if (t < 0){
            return 0ll;
        }
        int idx = upper_bound(bend(dif), t) - dif.begin();
        int cnt = isz(dif) - idx;
        ll area = (2ll * a[n].x + t) - (2ll * a[1].x - t) + 1;
        area -= (idx != isz(dif) ? suffdif[idx] : 0ll) * 2;
        area += (2 * t + 1) * cnt;
        area *= (2 * t + 1);
        return (area - (cnt + 1)) / 2 + (cnt + 1);
    }

    void solve(){
        sort(a + 1, a + n + 1, [&](const point& p, const point& q){
            return p.x < q.x;
        });
        ForE(i, 2, n){
            dif.emplace_back(a[i].x - a[i - 1].x);
        }
        sort(bend(dif));
        suffdif = vector <ll>(bend(dif));
        FordE(i, isz(suffdif) - 2, 0){
            suffdif[i] += suffdif[i + 1];
        }
        ForE(i, 1, q){
            ll ans = count_dist(b[i]) - count_dist(b[i] - 1);
            cout << ans << "\n";
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    cin >> n >> q;
    ForE(i, 1, n){
        cin >> a[i].x >> a[i].y;
    }
    ForE(i, 1, q){
        cin >> b[i];
    }

    if (subtask34::check()){
        subtask34::solve();
        return 0;
    }
}

/*
==================================================+
INPUT                                             |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

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