Submission #862325

#	Time	Username	Problem	Language	Result	Execution time	Memory
862325		sleepntsheep	Meteors (POI11_met)	C++17	100 / 100	1206 ms	33036 KiB

met

#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 (stderr)

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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13