oj.uz

답안 #862325

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
862325 2023-10-18T04:10:09 Z sleepntsheep Meteors (POI11_met) C++17
100 / 100
 1206 ms 33036 KB 
#include <bits/stdc++.h>

template <class T>
struct BIT
{
    int n;
    std::vector<T> a;
    BIT(int m) : n(1+m), a(2+m) {}
    void inc(int p, T x) { for (++p; p <= n; p+=p&-p) a[p] += x; }
    auto qry(int p, T z = 0) { for (++p; p; p-=p&-p) z+=a[p]; return z;}
};

int main()
{
    int n_state, n_sector, n_meteor;
    scanf("%d%d", &n_state, &n_sector);

    std::vector<std::vector<int>> states(n_state);
    std::vector<int> sample(n_state), ans(n_state, -1);

    for (int owner, i = 1; i <= n_sector; ++i)
        scanf("%d", &owner), states[--owner].push_back(i);
    for (int &x : sample) scanf("%d", &x);

    scanf("%d", &n_meteor);
    std::vector<std::tuple<int, int, int>> meteors(n_meteor);
    for (auto &[l, r, a] : meteors) scanf("%d%d%d", &l, &r, &a);

    BIT<int64_t> fw(n_sector + 20000);

    std::function<void(int, int, std::vector<int>&)> parallel_bs = [&](int l, int r, std::vector<int> &candi) {
        if (candi.empty()) return;

        auto m = l + (r-l)/2;

        for (int i = l; i <= m; ++i) {
            auto [ml, mr, ma] = meteors[i];
            fw.inc(ml, ma);
            fw.inc(mr + 1, -ma);
            if (ml > mr) fw.inc(1, ma), fw.inc(n_sector + 1, -ma);
        }

        std::vector<int> ok, not_ok;
        for (auto c : candi) {
            uint64_t sum = 0;
            for (auto st : states[c]) sum += fw.qry(st);
            if (sum >= sample[c]) ok.push_back(c), ans[c] = m;
            else not_ok.push_back(c), sample[c] -= sum;
        }

        for (int i = l; i <= m; ++i) {
            auto [ml, mr, ma] = meteors[i];
            ma *= -1;
            fw.inc(ml, ma);
            fw.inc(mr + 1, -ma);
            if (ml > mr) fw.inc(1, ma), fw.inc(n_sector + 1, -ma);
        }

        if (l != r)
        {
            parallel_bs(l, m, ok); std::vector<int>().swap(ok);
            parallel_bs(m+1, r, not_ok); std::vector<int>().swap(not_ok);
        }
    };

    std::vector<int> all(n_state);
    std::iota(all.begin(), all.end(), 0);
    parallel_bs(0, n_meteor - 1, all);

    for (int i = 0; i < n_state; ++i) 
    {
        if (ans[i] == -1) puts("NIE");
        else printf("%d\n", ans[i] + 1);
    }

    return 0;
}

Compilation message

met.cpp: In lambda function:
met.cpp:47:21: warning: comparison of integer expressions of different signedness: 'uint64_t' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   47 |             if (sum >= sample[c]) ok.push_back(c), ans[c] = m;
met.cpp: In function 'int main()':
met.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d%d", &n_state, &n_sector);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
met.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%d", &owner), states[--owner].push_back(i);
      |         ~~~~~^~~~~~~~~~~~~~
met.cpp:23:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     for (int &x : sample) scanf("%d", &x);
      |                           ~~~~~^~~~~~~~~~
met.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d", &n_meteor);
      |     ~~~~~^~~~~~~~~~~~~~~~~
met.cpp:27:42: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     for (auto &[l, r, a] : meteors) scanf("%d%d%d", &l, &r, &a);
      |                                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 3004 KB Output is correct
2 Correct 68 ms 5452 KB Output is correct
3 Correct 73 ms 3408 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 3188 KB Output is correct
2 Correct 74 ms 3160 KB Output is correct
3 Correct 51 ms 4812 KB Output is correct
4 Correct 20 ms 2896 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 2940 KB Output is correct
2 Correct 78 ms 5512 KB Output is correct
3 Correct 21 ms 1628 KB Output is correct
4 Correct 70 ms 3688 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 2652 KB Output is correct
2 Correct 81 ms 3156 KB Output is correct
3 Correct 38 ms 2744 KB Output is correct
4 Correct 92 ms 4768 KB Output is correct

Subtask #7
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 359 ms 22648 KB Output is correct
2 Correct 158 ms 11732 KB Output is correct
3 Correct 130 ms 4956 KB Output is correct
4 Correct 1193 ms 26460 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 373 ms 20444 KB Output is correct
2 Correct 242 ms 11092 KB Output is correct
3 Correct 55 ms 4896 KB Output is correct
4 Correct 1206 ms 33036 KB Output is correct