Submission #797083

#	Time	Username	Problem	Language	Result	Execution time	Memory
797083		vjudge1	Food Court (JOI21_foodcourt)	C++17	100 / 100	369 ms	53068 KiB

foodcourt

#include <bits/stdc++.h>

#define fi first
#define se second

const int N = 250500;
const int mod = 1e9 + 7;

using namespace std;

struct fenwick {
        vector<long long> t;
        fenwick(int _N) : t(_N, 0) {}

        void upd(int x, long long g) {
                while(x < t.size()) {
                        t[x] += g;
                        x += x & -x;
                }
        }

        long long get(int x) {
                long long res = 0;
                while(x > 0) {
                        res += t[x];
                        x -= x & -x;
                }
                return res;
        }

        int get_f(long long k) {
                int res = 0;
                for (int i = 20; i >= 0; i--) {
                        if (res + (1 << i) >= t.size()) {
                                continue;
                        } else if (t[res + (1 << i)] < k) {
                                res += (1 << i);
                                k -= t[res];
                        }
                }
                return res + 1;
        }
};

long long t[4 * N];
long long lz[4 * N];

void upd(int x, int l, int r, int tl, int tr, long long y)
{
        if (tl > tr) {
                return;
        } else if (l == tl && r == tr) {
                t[x] += y;
                lz[x] += y;
                return;
        }
        int m = (l + r) / 2;
        upd(x * 2, l, m, tl, min(m, tr), y);
        upd(x * 2 + 1, m + 1, r, max(m + 1, tl), tr, y);
        t[x] = min(t[x * 2], t[x * 2 + 1]) + lz[x];
}

long long inf = 1e18;
long long get(int x, int l, int r, int tl, int tr)
{
        if (tl > tr) {
                return inf;
        } else if (l == tl && r == tr) {
                return t[x];
        }
        int m = (l + r) / 2;
        return min(get(x * 2, l, m, tl, min(m, tr)), get(x * 2 + 1, m + 1, r, max(m + 1, tl), tr)) + lz[x];
}

fenwick A(N), B(N);

int n, m, q;
long long res[N];
long long c[N];
vector<pair<long long, long long>> ad[N];
vector<pair<long long, long long>> del[N];
vector<pair<long long, long long>> qu[N];


int main() {
        #ifdef zxc
            freopen("input.txt", "r", stdin);
            freopen("output.txt", "w", stdout);
        #endif
        ios_base::sync_with_stdio(0);

        cin >> n >> m >> q;
        for (int i = 1; i <= q; i++) {
                int t;
                cin >> t;
                res[i] = -1;
                if (t == 1) {
                        long long l, r, k;
                        cin >> l >> r >> c[i] >> k;
                        ad[l].push_back({i, k});
                        ad[r + 1].push_back({i, -k});
                } else if (t == 2) {
                        long long l, r, k;
                        cin >> l >> r >> k;
                        del[l].push_back({i, -k});
                        del[r + 1].push_back({i, k});
                } else {
                        long long l, b;
                        cin >> l >> b;
                        qu[l].push_back({i, b});
                }
        }

        for (int i = 1; i <= n; i++) {
                for (auto p: ad[i]) {
                        A.upd(p.fi, p.se);
                        B.upd(p.fi, p.se);
                        upd(1, 0, q, p.fi, q, p.se);
                }
                for (auto p: del[i]) {
                        B.upd(p.fi, p.se);
                        upd(1, 0, q, p.fi, q, p.se);
                }
                for (auto p: qu[i]) {
                        long long all = A.get(p.fi);
                        long long cur = B.get(p.fi) - get(1, 0, q, 0, p.fi);

                        p.se += all - cur;

                        if (p.se <= all) {
                                res[p.fi] = c[A.get_f(p.se)];
                        } else {
                                res[p.fi] = 0;
                        }
                }
        }

        for (int i = 1; i <= q; i++) {
                if (res[i] != -1) {
                        cout << res[i] << "\n";
                }
        }
}

Compilation message (stderr)

foodcourt.cpp: In member function 'void fenwick::upd(int, long long int)':
foodcourt.cpp:16:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |                 while(x < t.size()) {
      |                       ~~^~~~~~~~~~
foodcourt.cpp: In member function 'int fenwick::get_f(long long int)':
foodcourt.cpp:34:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |                         if (res + (1 << i) >= t.size()) {
      |                             ~~~~~~~~~~~~~~~^~~~~~~~~~~

• 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