QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#696813 | #6692. Building Company | pppwolf# | RE | 0ms | 3480kb | C++23 | 2.8kb | 2024-11-01 02:20:48 | 2024-11-01 02:20:50 |
Judging History
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...