QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#535453#9228. ICPC InferencejianglyTL 0ms3828kbC++202.6kb2024-08-28 02:51:242024-08-28 02:51:25

Judging History

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

  • [2024-08-28 02:51:25]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3828kb
  • [2024-08-28 02:51:24]
  • 提交

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...

output:


result: