Submission #427037

#	Time	Username	Problem	Language	Result	Execution time	Memory
427037		KoD	Food Court (JOI21_foodcourt)	C++17	100 / 100	508 ms	40260 KiB

foodcourt

#include <bits/stdc++.h>

using ll = long long;

template <class T> using Vec = std::vector<T>;

constexpr ll INF = std::numeric_limits<ll>::max() / 2;

struct Fenwick {
    Vec<ll> data;
    explicit Fenwick(const int n): data(n + 1) {}
    void add(int i, const ll x) {
        for (++i; i < (int) data.size(); i += i & -i) {
            data[i] += x;
        }
    }
    ll get(int i) const {
        ll x = 0;
        for (; i > 0; i -= i & -i) {
            x += data[i];
        }
        return x;
    }
    int lower_bound(ll x) const {
        int i = 1, j = 0;
        while (2 * i < (int) data.size()) {
            i <<= 1;
        }
        while (i > 0) {
            if (j + i < (int) data.size() and x > data[j + i]) {
                j += i;
                x -= data[j];
            }
            i >>= 1;
        }
        return j + 1;
    }
};

struct Func {
    ll add, lb;
    explicit Func(const ll a = 0, const ll l = -INF) : add(a), lb(l) {}
    Func composite(const Func& old) const {
        return Func(old.add + add, std::max(old.lb + add, lb));
    }
};

struct Segtree {
    int size;
    Vec<Func> data;
    explicit Segtree(const int n) : size(n), data(2 * n) {}
    void flush(const int k) {
        data[2 * k] = data[k].composite(data[2 * k]);
        data[2 * k + 1] = data[k].composite(data[2 * k + 1]);
        data[k] = Func();
    }
    void push(const int k) {
        const int lsb = __builtin_ctz(k);
        const int width = 31 - __builtin_clz(k);
        for (int d = width; d > lsb; --d) {
            flush(k >> d);
        }
    }
    void operate(int l, int r, const Func& f) {
        l += size;
        r += size;
        push(l);
        push(r);
        while (l < r) {
            if (l & 1) {
                data[l] = f.composite(data[l]);
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                data[r] = f.composite(data[r]);
            }
            l >>= 1;
            r >>= 1;
        }
    }
    ll get(int i) const {
        i += size;
        Func ret;
        while (i > 0) {
            ret = data[i].composite(ret);
            i >>= 1;
        }
        return std::max(ret.add, ret.lb);
    }
};

int scan_int() {
    int x;
    std::scanf("%d", &x);
    return x;
}

ll scan_ll() {
    ll x;
    std::scanf("%lld", &x);
    return x;
}

void print(const int x) {
    std::printf("%d\n", x);
}

int main() {
    const int N = scan_int();
    const int M = scan_int();
    const int Q = scan_int();
    Fenwick whole(N);
    Segtree real(N);
    Vec<int> ans, group;
    ans.reserve(Q);
    group.reserve(Q);
    Vec<Vec<std::pair<int, ll>>> query(N), add(N);
    for (int i = 0; i < Q; ++i) {
        const int t = scan_int();
        if (t == 1) {
            const int l = scan_int() - 1;
            const int r = scan_int();
            const int c = scan_int();
            const ll k = scan_ll();
            whole.add(l, k);
            whole.add(r, -k);
            real.operate(l, r, Func(k));
            add[l].emplace_back((int) group.size(), k);
            if (r != N) {
                add[r].emplace_back((int) group.size(), -k);
            }
            group.push_back(c);
        } else if (t == 2) {
            const int l = scan_int() - 1;
            const int r = scan_int();
            const ll k = scan_ll();
            real.operate(l, r, Func(-k, 0));
        } else {
            const int a = scan_int() - 1;
            const ll b = scan_ll();
            const ll d = real.get(a) - b;
            if (d >= 0) {
                query[a].emplace_back((int) ans.size(), whole.get(a + 1) - d);
            }
            ans.push_back(0);
        }
        // for (int j = 0; j < N; ++j) {
        //     std::cerr << real.get(j) << " \n"[j + 1 == N];
        // }
    }
    Fenwick fen((int) group.size());
    for (int i = 0; i < N; ++i) {
        for (const auto [j, x] : add[i]) {
            fen.add(j, x);
        }
        for (const auto [j, x] : query[i]) {
            // std::cerr << j << ' ' << x << '\n';
            ans[j] = group[fen.lower_bound(x) - 1];
        }
    }
    for (const int x : ans) {
        print(x);
    }
    return 0;
}

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:111:15: warning: unused variable 'M' [-Wunused-variable]
  111 |     const int M = scan_int();
      |               ^
foodcourt.cpp: In function 'int scan_int()':
foodcourt.cpp:95:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     std::scanf("%d", &x);
      |     ~~~~~~~~~~^~~~~~~~~~
foodcourt.cpp: In function 'll scan_ll()':
foodcourt.cpp:101:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |     std::scanf("%lld", &x);
      |     ~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11