QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#946352#6692. Building CompanyHiraethsoul#RE 0ms0kbC++204.1kb2025-03-21 20:16:002025-03-21 20:16:00

Judging History

This is the latest submission verdict.

  • [2025-03-21 20:16:00]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2025-03-21 20:16:00]
  • Submitted

answer

#include <bits/stdc++.h>

#define int long long
signed main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    int g;
    std::cin >> g;
    std::vector<int> cur;
    std::vector<std::pair<int, int>> init(g + 1);
    for (int i = 1; i <= g; ++i)
    {
        std::cin >> init[i].first >> init[i].second;
        cur.push_back(init[i].first);
    }
    int n;
    std::cin >> n;
    std::vector<int> re(n + 1, 0);
    std::vector<std::vector<std::pair<int, int>>> tt(n + 1);
    std::vector<std::vector<std::pair<int, int>>> require(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        int m;
        std::cin >> m;
        re[i] = m;
        for (int j = 1; j <= m; ++j)
        {
            int x, y;
            std::cin >> x >> y;
            cur.push_back(x);
            require[i].push_back({x, y});
        }
        int k;
        std::cin >> k;
        for (int j = 1; j <= k; ++j)
        {
            int x, y;
            std::cin >> x >> y;
            cur.push_back(x);
            tt[i].push_back({x, y});
        }
    }

    std::sort(begin(cur), end(cur));
    cur.erase(std::unique(begin(cur), end(cur)), end(cur));
    for (int i = 1; i <= g; ++i)
    {
        init[i].first = std::lower_bound(begin(cur), end(cur), init[i].first) - begin(cur) + 1;
    }
    int max = cur.size();
    for (int i = 1; i <= n; ++i)
    {
        for (auto &[x, y] : require[i])
        {
            x = std::lower_bound(begin(cur), end(cur), x) - begin(cur) + 1;
        }
        for (auto &[x, y] : tt[i])
        {
            x = std::lower_bound(begin(cur), end(cur), x) - begin(cur) + 1;
        }
    }
    std::vector<std::vector<std::pair<int, int>>> RE(max + 1);

    for (int i = 1; i <= n; ++i)
    {
        for (auto [x, y] : require[i])
        {
            RE[x].push_back({y, i});
        }
    }
    for (int i = 1; i <= max; ++i)
    {
        std::sort(begin(RE[i]), end(RE[i]));
    }
    std::vector<int> last(max + 1, -1);
    std::vector<int> cnt(n + 1, 0);
    std::vector<int> now(max + 1, 0);
    for (int i = 1; i <= g; ++i)
    {
        now[init[i].first] = init[i].second;
    }
    int res = 0;
    auto work = [&](int id)
    {
        for (auto [x, y] : tt[id])
        {
            now[x] += y;
        }
    };
    auto Work = [&](auto Work, int x) -> void
    {
        int L = last[x] + 1, R = RE[x].size() - 1;
        int ans = L - 1;
        while (L <= R)
        {
            int mid = L + R >> 1;
            if (RE[x][mid].first <= now[x])
            {
                L = mid + 1;
                ans = mid;
            }
            else
            {
                R = mid - 1;
            }
        }
        for (int j = last[x] + 1; j <= ans; ++j)
        {
            int id = RE[x][j].second;
            +cnt[id]++;
            if (cnt[id] == re[id])
            {
                ++res;
                work(id);
                Work(Work, id);
            }
        }
        last[x] = ans;
    };
    for (int i = 1; i <= n; ++i)
    {
        if (re[i] == 0)
        {
            ++res;
            work(i);
            for (auto [xx, yy] : tt[i])
            {
                Work(Work, xx);
            }
        }
    }
    for (int i = 1; i <= max; ++i)
    {
        int L = last[i] + 1, R = RE[i].size() - 1;
        int ans = L - 1;
        while (L <= R)
        {
            int mid = L + R >> 1;
            if (RE[i][mid].first <= now[i])
            {
                L = mid + 1;
                ans = mid;
            }
            else
            {
                R = mid - 1;
            }
        }
        for (int j = last[i] + 1; j <= ans; ++j)
        {
            int id = RE[i][j].second;
            cnt[id]++;
            if (cnt[id] == re[id])
            {
                ++res;
                work(id);
                for (auto [xx, yy] : tt[id])
                {
                    Work(Work, xx);
                }
            }
        }
        last[i] = ans;
    }
    std::cout << res << '\n';
}

詳細信息

Test #1:

score: 0
Runtime Error

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:


result: