QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#946352 | #6692. Building Company | Hiraethsoul# | RE | 0ms | 0kb | C++20 | 4.1kb | 2025-03-21 20:16:00 | 2025-03-21 20:16:00 |
Judging History
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