QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#535453 | #9228. ICPC Inference | jiangly | TL | 0ms | 3828kb | C++20 | 2.6kb | 2024-08-28 02:51:24 | 2024-08-28 02:51:25 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
constexpr int K = 20;
constexpr i64 M = 1E16;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, D, L;
std::cin >> N >> D >> L;
std::vector<std::vector<int>> vec(D);
for (int i = 0; i < N; i++) {
int d, t;
std::cin >> d >> t;
d--;
vec[d].push_back(t);
}
std::vector<i64> bronze(D), gold(D);
std::vector<int> teams;
for (int i = 0; i < D; i++) {
if (vec[i].empty()) {
continue;
}
teams.push_back(i);
}
for (auto i : teams) {
bronze[i] = M - vec[i].back() - (vec[i].size() - 1) * K;
for (int j = 0; j < std::min<int>(vec[i].size(), 13); j++) {
gold[i] += M - vec[i][j];
}
}
i64 ans = 0;
std::vector<i64> b, g;
for (auto i : teams) {
b.push_back(bronze[i]);
}
std::sort(b.begin(), b.end());
i64 tot = 0;
for (auto i : teams) {
if (vec[i].empty()) {
continue;
}
tot += std::upper_bound(b.begin(), b.end(), gold[i]) - b.begin();
tot--;
}
for (auto i : teams) {
std::vector<i64> s;
for (int j = 0; j < vec[i].size(); j++) {
for (int k = 0; k <= j; k++) {
s.push_back(M - vec[i][j] - k * K);
}
}
if (vec[i].size() >= 2) {
s.push_back(2 * M - vec[i][0] - vec[i][1]);
}
std::sort(s.begin(), s.end());
ans += tot;
auto check = [&](i64 l, i64 r) {
for (auto b : teams) {
for (auto g : teams) {
if (l < bronze[b] && bronze[b] <= gold[g] && gold[g] < r) {
ans--;
}
}
}
for (auto j : teams) {
if (l < bronze[j] && bronze[j] <= gold[j] && gold[j] < r) {
ans++;
}
}
};
check(0, s[0]);
for (int j = 1; j < s.size(); j++) {
check(s[j - 1], s[j]);
}
check(s.back(), 1E18);
for (auto j : teams) {
if (gold[j] >= bronze[i]) {
ans--;
}
}
for (auto j : teams) {
if (bronze[j] <= gold[i]) {
ans--;
}
}
ans += 2;
}
std::cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3508kb
input:
4 3 300 1 10 2 25 2 30 3 50
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
4 6 200000 6 1 6 1 1 2 2 2
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: -100
Time Limit Exceeded
input:
191580 64997 56 24878 1 35060 1 24245 1 64330 1 9650 1 15423 1 34953 1 21456 1 36718 1 21395 1 17613 1 16995 1 45257 1 31277 1 20026 1 1870 1 25581 1 9997 1 54701 1 30752 1 32269 1 705 1 64186 1 58881 1 24614 1 55311 1 18259 1 58886 1 23296 1 17628 1 3411 1 37469 1 47951 1 12188 1 60720 1 54168 1 45...