oj.uz

Submission #869605

# Submission time Handle Problem Language Result Execution time Memory
869605 2023-11-05T03:12:37 Z riariti Meteors (POI11_met) C++17
0 / 100
 6000 ms 46896 KB 
#include <bits/stdc++.h>

#ifdef local
#include "../local.hpp"
#else
#define dbg(...)
#endif

using i64 = long long;

namespace cplib {
template <typename T> class fenwick_tree {
  protected:
    std::size_t n;
    std::vector<T> a;

    void init(std::size_t n_) {
        n = n_;
        a.assign(n, T{});
    }

  public:
    fenwick_tree() { init(std::size_t(0)); }
    explicit fenwick_tree(std::size_t _n) { init(_n); }

    void add(std::size_t x, const T &v) {
        for (std::size_t i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }

    T sum(std::size_t x) {
        T ans{};
        for (std::size_t i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }

    T sum(std::size_t l, std::size_t r) { return sum(r) - sum(l); }

    std::size_t select(const T &k) {
        std::size_t x = 0;
        T cur{};
        for (std::size_t i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};
} // namespace cplib

int32_t main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);

    int n, m;
    std::cin >> n >> m;
    std::vector<int> o(m);
    for (int i = 0; i < m; i++) {
        auto &x = o[i];
        std::cin >> x;
    }
    std::vector<int> p(n);
    for (int i = 0; i < n; i++) {
        auto &x = p[i];
        std::cin >> x;
    }
    int k;
    std::cin >> k;
    std::vector<std::array<int, 3>> lra(k);
    for (int i = 0; i < k; i++) {
        auto &[l, r, a] = lra[i];
        std::cin >> l >> r >> a;
        l--;
        r--;
    }

    std::map<int, std::vector<int>> ow;
    for (int i = 0; i < m; i++) {
        auto x = o[i];

        ow[x].push_back(i);
    }

    cplib::fenwick_tree<int> fw(m);

    std::vector<std::array<int, 2>> lr(n);
    for (int i = 0; i < n; i++) {
        lr[i] = {0, k - 1 + 1};
    }

    bool chk = true;
    while (chk) {
        chk = false;
        fw = cplib::fenwick_tree<int>(m);

        std::map<int, std::vector<int>> op;
        for (int i = 0; i < n; i++) {
            auto [l, r] = lr[i];
            if (l == r) {
                continue;
            }

            int m = l + (r - l) / 2;
            op[m].push_back(i);
        }

        for (int i = 0; i < k; i++) {
            {
                auto [l, r, a] = lra[i];

                if (l <= r) {
                    fw.add(l, a);
                    fw.add(r + 1, -a);
                } else {
                    fw.add(l, a);
                    fw.add(0, a);
                    fw.add(r + 1, -a);
                }
            }

            auto &v = op[i];
            while (!v.empty()) {
                chk = true;

                auto x = *v.begin();
                v.erase(v.begin());

                int sum = 0;
                for (auto oo : ow[x]) {
                    oo += fw.sum(oo);

                    if (oo >= p[x]) {
                        break;
                    }
                }

                if (sum >= p[x]) {
                    lr[x][1] = i + 1;
                } else {
                    lr[x][0] = i;
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        auto [l, r] = lr[i];

        if (l < k) {
            std::cout << l + 1 << "\n";
        } else {
            std::cout << "NIE\n";
        }
    }

    return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6046 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6007 ms 600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6088 ms 6864 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6045 ms 7412 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6066 ms 6808 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6051 ms 6348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6018 ms 46896 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6039 ms 45900 KB Time limit exceeded
2 Halted 0 ms 0 KB -