#902681 (C++17) No.2422 regisys?

提出ソース

結果

問題	No.2422 regisys?
ユーザー	Cyanmond
提出日時	2023-08-12 14:41:46
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	142 ms / 2,000 ms
コード長	13,823 bytes
コンパイル時間	2,888 ms
コンパイル使用メモリ	223,908 KB
実行使用メモリ	10,504 KB
最終ジャッジ日時	2024-11-19 20:58:17
合計ジャッジ時間	7,972 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	2 ms 5,248 KB
testcase_08	AC	2 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	2 ms 5,248 KB
testcase_12	AC	2 ms 5,248 KB
testcase_13	AC	3 ms 5,248 KB
testcase_14	AC	2 ms 5,248 KB
testcase_15	AC	2 ms 5,248 KB
testcase_16	AC	2 ms 5,248 KB
testcase_17	AC	2 ms 5,248 KB
testcase_18	AC	2 ms 5,248 KB
testcase_19	AC	2 ms 5,248 KB
testcase_20	AC	3 ms 5,248 KB
testcase_21	AC	2 ms 5,248 KB
testcase_22	AC	2 ms 5,248 KB
testcase_23	AC	2 ms 5,248 KB
testcase_24	AC	2 ms 5,248 KB
testcase_25	AC	2 ms 5,248 KB
testcase_26	AC	2 ms 5,248 KB
testcase_27	AC	2 ms 5,248 KB
testcase_28	AC	2 ms 5,248 KB
testcase_29	AC	2 ms 5,248 KB
testcase_30	AC	3 ms 5,248 KB
testcase_31	AC	47 ms 6,016 KB
testcase_32	AC	67 ms 6,444 KB
testcase_33	AC	43 ms 5,760 KB
testcase_34	AC	30 ms 5,248 KB
testcase_35	AC	53 ms 6,656 KB
testcase_36	AC	50 ms 5,632 KB
testcase_37	AC	69 ms 6,880 KB
testcase_38	AC	52 ms 5,580 KB
testcase_39	AC	36 ms 5,248 KB
testcase_40	AC	29 ms 5,248 KB
testcase_41	AC	35 ms 5,248 KB
testcase_42	AC	88 ms 9,032 KB
testcase_43	AC	49 ms 5,632 KB
testcase_44	AC	96 ms 9,360 KB
testcase_45	AC	80 ms 7,584 KB
testcase_46	AC	96 ms 9,328 KB
testcase_47	AC	60 ms 6,400 KB
testcase_48	AC	97 ms 9,452 KB
testcase_49	AC	77 ms 7,468 KB
testcase_50	AC	87 ms 9,240 KB
testcase_51	AC	125 ms 9,264 KB
testcase_52	AC	43 ms 6,144 KB
testcase_53	AC	98 ms 9,168 KB
testcase_54	AC	134 ms 10,504 KB
testcase_55	AC	99 ms 9,272 KB
testcase_56	AC	92 ms 7,992 KB
testcase_57	AC	142 ms 9,980 KB
testcase_58	AC	140 ms 9,860 KB
testcase_59	AC	142 ms 9,852 KB
testcase_60	AC	141 ms 9,860 KB
testcase_61	AC	2 ms 5,248 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#line 1 "main.cpp"
#include <bits/stdc++.h>

#line 2 "template.cpp"

#pragma region templates

#pragma region std::vector operator

template <class T>
std::vector<T> &operator++(std::vector<T> &v) {
    for (auto &e : v) {
        ++e;
    }
    return v;
}

template <class T>
std::vector<T> operator++(std::vector<T> &v, int) {
    auto res = v;
    for (auto &e : v) {
        ++e;
    }
    return res;
}

template <class T>
std::vector<T> &operator--(std::vector<T> &v) {
    for (auto &e : v) {
        --e;
    }
    return v;
}

template <class T>
std::vector<T> operator--(std::vector<T> &v, int) {
    auto res = v;
    for (auto &e : v) {
        --e;
    }
    return res;
}

#pragma endregion

#pragma region ios

namespace scanner {

namespace submodule {
void read(int &a) {
    std::cin >> a;
}

void read(long long &a) {
    std::cin >> a;
}

void read(char &a) {
    std::cin >> a;
}

void read(double &a) {
    std::cin >> a;
}

void read(std::string &a) {
    std::cin >> a;
}

template <class T, class S>
void read(std::pair<T, S> &p) {
    read(p.first);
    read(p.second);
}

template <class T>
void read(std::vector<T> &);

template <class T>
void read(std::vector<T> &a) {
    for (auto &e : a) {
        read(e);
    }
}

template <class T>
void read(T &a) {
    std::cin >> a;
}
} // namespace submodule

void scan() {}

template <class Head, class... Tail>
void scan(Head &head, Tail &...tail) {
    submodule::read(head);
    scan(tail...);
}

void scanI() {}

template <class Head, class... Tail>
void scanI(Head &head, Tail &...tail) {
    submodule::read(head);
    --head;
    scanI(tail...);
}

} // namespace scanner

template <class T, class U>
std::ostream &operator<<(std::ostream &os, std::pair<T, U> pa) {
    os << '{' << pa.first << ", " << pa.second << '}';
    return os;
}

template <class T>
std::ostream &operator<<(std::ostream &os, std::vector<T> vec) {
    os << "{";
    const int n = (int)vec.size();
    for (int i = 0; i < n; i++) {
        os << vec[i];
        os << (i == n - 1 ? "}" : ", ");
    }
    return os;
}

template <class T, std::size_t S>
std::ostream &operator<<(std::ostream &os, std::array<T, S> arr) {
    os << "{";
    for (int i = 0; i < (int)S; i++) {
        os << arr[i];
        os << (i == S - 1 ? "}" : ", ");
    }
    os << "}";
    return os;
}

template <class T, class U>
std::ostream &operator<<(std::ostream &os, std::map<T, U> ma) {
    os << "{";
    auto itr = ma.begin();
    while (itr != ma.end()) {
        os << *itr << (itr == --ma.end() ? "}" : ", ");
        ++itr;
    }
    return os;
}

template <class T>
std::ostream &operator<<(std::ostream &os, std::set<T> st) {
    os << "{";
    auto itr = st.begin();
    while (itr != st.end()) {
        os << *itr << (itr == --st.end() ? "}" : ", ");
        ++itr;
    }
    return os;
}

namespace printer {
void print() {
    std::cout << '\n';
}
template <class Head, class... Tail>
void print(const Head &head, const Tail &...tail) {
    std::cout << head;
    if (sizeof...(tail))
        std::cout << ' ';
    print(tail...);
}

} // namespace printer

namespace dumper {
void dumpFunc() {
    std::cerr << std::endl;
}

template <class Head, class... Tail>
void dumpFunc(Head &&head, Tail &&...tail) {
    std::cerr << head;
    if (sizeof...(Tail) == 0) {
        std::cerr << ' ';
    } else {
        std::cerr << ", ";
    }
    dumpFunc(std::move(tail)...);
}
} // namespace dumper

#pragma endregion

#pragma region functions

template <class T>
constexpr int si(const T &c) {
    return static_cast<int>(c.size());
}

template <class T>
constexpr bool afMin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
constexpr bool afMax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template <class T = long long, class S>
constexpr T calcSum(const S &container) {
    return std::accumulate(container.begin(), container.end(), static_cast<T>(0));
}

template <class T>
constexpr auto calcMin(const T &container) {
    return *std::min_element(container.begin(), container.end());
}

template <class T>
constexpr auto calcMax(const T &container) {
    return *std::max_element(container.begin(), container.end());
}

template <class T>
constexpr int lwbi(const T &container, const typename T::value_type &value) {
    return static_cast<int>(std::distance(container.cbegin(), std::lower_bound(container.cbegin(), container.cend(), value)));
}

template <class T>
constexpr int upbi(const T &container, const typename T::value_type &value) {
    return static_cast<int>(std::distance(container.cbegin(), std::upper_bound(container.cbegin(), container.cend(), value)));
}

template <class T>
auto makeVec(const int n, const T &value) {
    return std::vector(n, value);
}

template <class... Args>
auto makeVec(const int n, Args... args) {
    return std::vector(n, makeVec(args...));
}

template <class T, class F>
T binarySearch(T ok, T ng, const F &f) {
    while (abs(ok - ng) > 1) {
        T mid = ok + ng >> 1;
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

template <class T, class F>
T binarySearchReal(T ok, T ng, const F &f, int iter = 80) {
    while (iter--) {
        T mid = (ok + ng) / 2;
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

#pragma endregion

#pragma region macros and vars

using namespace scanner;
using namespace printer;
using i64 = long long;

template <class T>
using Vec = std::vector<T>;
template <class T>
using PQ = std::priority_queue<T>;
template <class T>
using RPQ = std::priority_queue<T, std::vector<T>, std::greater<T>>;

std::mt19937 mtRand(std::random_device{}());
constexpr std::array<std::pair<int, int>, 4> dxy4 = {{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}};
constexpr std::array<std::pair<int, int>, 8> dxy8 = {
    {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}}};

#define INT(...)                                                                                                       \
    int __VA_ARGS__;                                                                                                   \
    scan(__VA_ARGS__)
#define INTI(...)                                                                                                      \
    int __VA_ARGS__;                                                                                                   \
    scanI(__VA_ARGS__)
#define I64(...)                                                                                                        \
    i64 __VA_ARGS__;                                                                                                    \
    scan(__VA_ARGS__)
#define I64I(...)                                                                                                       \
    i64 __VA_ARGS__;                                                                                                    \
    scanI(__VA_ARGS__)
#define STR(...)                                                                                                       \
    std::string __VA_ARGS__;                                                                                                \
    scan(__VA_ARGS__)
#define CHR(...)                                                                                                       \
    char __VA_ARGS__;                                                                                                  \
    scan(__VA_ARGS__)
#define DOUBLE(...)                                                                                                    \
    double __VA_ARGS__;                                                                                                \
    scan(__VA_ARGS__)
#define VEC(type, name, n)                                                                                             \
    std::vector<type> name(n);                                                                                         \
    scan(name)
#define VECI(type, name, n)                                                                                            \
    std::vector<type> name(n);                                                                                         \
    scanI(name)
#define VEC2(type, name1, name2, n)                                                                                    \
    std::vector<type> name1(n), name2(n);                                                                              \
    for (int i = 0; i < n; i++)                                                                                        \
    scan(name1[i], name2[i])
#define VEC2I(type, name1, name2, n)                                                                                   \
    std::vector<type> name1(n), name2(n);                                                                              \
    for (int i = 0; i < n; i++)                                                                                        \
    scanI(name1[i], name2[i])
#define VEC3(type, name1, name2, name3, n)                                                                             \
    std::vector<type> name1(n), name2(n), name3(n);                                                                    \
    for (int i = 0; i < n; i++)                                                                                        \
    scan(name1[i], name2[i], name3[i])
#define VEC3I(type, name1, name2, name3, n)                                                                            \
    std::vector<type> name1(n), name2(n), name3(n);                                                                    \
    for (int i = 0; i < n; i++)                                                                                        \
    scanI(name1[i], name2[i], name3[i])
#define VEC4(type, name1, name2, name3, name4, n)                                                                      \
    std::vector<type> name1(n), name2(n), name3(n), name4(n);                                                          \
    for (int i = 0; i < n; i++)                                                                                        \
        scan(name1[i], name2[i], name3[i], name4[i]);
#define VEC4I(type, name1, name2, name3, name4, n)                                                                     \
    std::vector<type> name1(n), name2(n), name3(n), name4(n);                                                          \
    for (int i = 0; i < n; i++)                                                                                        \
        scanI(name1[i], name2[i], name3[i], name4[i]);
#define VV(type, name, h, w)                                                                                           \
    std::vector<std::vector<type>> name(h, std::vector<type>(w));                                                      \
    scan(name)
#define VVI(type, name, h, w)                                                                                          \
    std::vector<std::vector<type>> name(h, std::vector<type>(w));                                                      \
    scanI(name)

#define overload5(a, b, c, d, e, name, ...) name
#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define per(i, l, r) for (int i = (r - 1); i >= (l); --i)
#define fore0(a) rep (a.size())
#define fore1(i, a) for (auto &&i : a)
#define fore2(a, b, v) for (auto &&[a, b] : v)
#define fore3(a, b, c, v) for (auto &&[a, b, c] : v)
#define fore4(a, b, c, d, v) for (auto &&[a, b, c, d] : v)
#define fore(...) overload5(__VA_ARGS__, fore4, fore3, fore2, fore1, fore0)(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#define mp std::make_pair
#define ALL(x) (x).begin(), (x).end()
#define UNIQUE(x) (x).erase(std::unique((x).begin(), (x).end()), (x).end())
#define fi first
#define se second

#define dump(...)                                                                                                      \
    std::cerr << ' ';                                                                                                  \
    std::cerr << #__VA_ARGS__ << " : [" << __LINE__ << " : " << __FUNCTION__ << "]" << std::endl;                       \
    std::cerr << "    ";                                                                                               \
    dumper::dumpFunc(__VA_ARGS__)

#pragma endregion

#pragma endregion
#line 4 "main.cpp"

struct MakeIOFast {
    MakeIOFast() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        std::cout << std::fixed << std::setprecision(15);
    }
} makeIOFastv;

using namespace std;

int main() {
    INT(N, M);
    VEC(int, A, N);
    VEC(int, B, N);
    VEC2(int, T, C, M);

    vector<int> X, Y;
    rep (i, 0, M) {
        if (T[i] == 0) X.pb(C[i]);
        else Y.pb(C[i]);
    }
    vector<pair<int, int>> D(N);
    rep (i, 0, N) D[i] = {A[i], B[i]};
    sort(ALL(D));
    sort(ALL(X));
    sort(ALL(Y));

    priority_queue<pair<int, int>> pq;
    const int U = si(X), V = si(Y);
    vector<bool> used(N);
    int r = 0, ans = 0;
    rep (i, 0, U) {
        while (r != N and D[r].first <= X[i]) {
            pq.push({D[r].second, r});
            ++r;
        }
        if (pq.empty()) continue;
        const auto j = pq.top().second;
        pq.pop();
        used[j] = true;
        ++ans;
    }

    vector<i64> O;
    rep (i, 0, N)
        if (not used[i]) O.pb(D[i].second);
    const int E = si(O);
    sort(ALL(O));
    r = 0;
    int cnt = 0;
    rep (i, 0, V) {
        while (r != E and O[r] <= Y[i]) {
            ++cnt;
            ++r;
        }
        if (cnt >= 1) {
            ++ans;
            --cnt;
        }
    }
    print(N - ans);
}

yukicoder

結果

テストケース

ソースコード