QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#696813#6692. Building Companypppwolf#RE 0ms3480kbC++232.8kb2024-11-01 02:20:482024-11-01 02:20:50

Judging History

你现在查看的是最新测评结果

  • [2024-11-01 02:20:50]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3480kb
  • [2024-11-01 02:20:48]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;

template <class T>
struct Discretization {
    int n;
    std::vector<T> a;
    Discretization(std::vector<T> _) {
        a = _;
        std::sort(a.begin(), a.end());
        a.erase(std::unique(a.begin(), a.end()), a.end());
        n = int(_.size());
    }

    int find(int x) {
        return std::lower_bound(a.begin(), a.end(), x) - a.begin();
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int g;
    std::cin >> g;

    std::map<int, int> map;
    std::vector<int> ord(g);
    for (int i = 0; i < g; ++i) {
        int t, u;
        std::cin >> t >> u;
        ord[i] = t;
        map[u]++;
    }

    Discretization<int> disc(ord);

    int n;
    std::cin >> n;

    std::vector<std::pair<int, int>> can(n);
    std::vector<std::set<std::pair<int, int>>> set(n);
    std::vector<std::vector<std::pair<int, int>>> get(n);
    std::set<std::pair<int, int>> tset;
    for (int i = 0; i < n; ++i) {
        int m;
        std::cin >> m;

        can[i].first = m;
        int cnt = 0;
        std::vector<int> a(m), b(m);
        for (int j = 0; j < m; ++j) {
            std::cin >> a[i] >> b[i];
            cnt += map[a[i]] >= b[i];
        }
        can[i].second = cnt;

        int k;
        std::cin >> k;

        for (int j = 0; j < k; ++j) {
            int c, d;
            std::cin >> c >> d;
            get[i].emplace_back(c, d);
        }
        if (cnt != m) {
            for (int j = 0; j < m; ++j) {
                if (map[a[i]] < b[i]) {
                    int y = disc.find(a[i]);
                    set[y].emplace(b[i], i);
                }
            }
            tset.emplace(0, i);
        } else {
            tset.emplace(1, i);
        }
    }

    // for (auto [i, j] : tmap) {
    //     map[i] += j;
    //     int y = disc.find(i);
    //     while (!set[y].empty() && map[i] >= set[y].begin()->first) {
    //         auto [u, v] = *set[y].begin();
    //         set[y].erase({u, v});


    //     }
    // }

    while (!tset.empty() && tset.rbegin()->first) {
        auto [_, i] = *tset.rbegin();
        tset.erase({_, i});

        for (auto [c, d] : get[i]) {
            int y = disc.find(c);
            map[c] += d;
            while (!set[y].empty() && map[c] >= set[y].begin()->first) {
                auto [u, v] = *set[y].begin();
                set[y].erase({u, v});

                if (++can[v].second == can[v].first) {
                    auto [i1, j1] = *tset.find({0, v});
                    tset.erase({i1, j1});
                    tset.emplace(1, v);
                }
            }
        }
    }

    std::cout << n - tset.size();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3480kb

input:

2 2 1 1 2
5
1 3 1
0
2 1 1 2 1
2 3 2 2 1
3 1 5 2 3 3 4
1 2 5
3 2 1 1 1 3 4
1 1 3
0
1 3 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: -100
Runtime Error

input:

3 610031727 590328742 816793299 18485566 654221125 47823436
10
3 610031727 224714165 816793299 491951703 654221125 593479446
1 610031727 538596643
1 610031727 551036304
3 816793299 262985484 610031727 52580932 654221125 424397787
1 654221125 889197190
3 654221125 126924193 610031727 963399336 816793...

output:


result: