답안 #396439

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
396439	2021-04-30T00:36:15 Z	12tqian	푸드 코트 (JOI21_foodcourt)	C++17	24 / 100	511 ms	158400 KB

foodcourt

#include <bits/stdc++.h>

using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int N = 5e5 + 5;

 

struct SumSeg {
    vl lz;
    vl st;
    int sz;

    void init(int n) {
        sz = 1;
        while (sz < n) sz <<= 1;
        lz.assign(2 * sz, 0);
        st.assign(2 * sz, 0);
    }

    void pull(int i) {
        st[i] = st[2 * i] + st[2 * i + 1];
    }

    void push(int i, int l, int r) {
        st[i] += (r - l + 1) * lz[i];
        if (l != r) { 
            lz[2 * i] += lz[i];
            lz[2 * i + 1] += lz[i];
        }
        lz[i] = 0;
    }

    void upd(int lo, int hi, ll inc, int i = 1, int l = 0, int r = -1) {
        if (r == -1) r += sz;
        push(i, l, r);
        if (hi < l || r < lo) return;
        if (lo <= l && r <= hi) {
            lz[i] = inc;
            push(i, l, r);
            return;
        }
        int m = (l + r) >> 1;
        upd(lo, hi, inc, 2 * i, l, m);
        upd(lo, hi, inc, 2 * i + 1, m + 1, r);
        pull(i);
    }

    ll query(int lo, int hi, int i = 1, int l = 0, int r = -1) {
        if (r == -1) r += sz;
        push(i, l, r);
        if (hi < l || r < lo) return 0;
        if (lo <= l && r <= hi) return st[i];
        int m = (l + r) >> 1;
        return query(lo, hi, 2 * i, l, m) + query(lo, hi, 2 * i + 1, m + 1, r);
    }
};

template <class C> struct SegmentTreeBeats {
    using T = std::pair<std::pair<C, C>, int>;
    const C INF = std::numeric_limits<C>::max();
    std::vector<C> mx_mod, mn_mod, mod, sum;
    std::vector<T> mx, mn;
    int sz; 

    void init(int sz_) {
        sz = 1; 
        while (sz < sz_) sz *= 2;
        mx_mod.assign(2 * sz, 0);
        mn_mod.assign(2 * sz, 0);
        mod.assign(2 * sz, 0);
        sum.assign(2 * sz, 0);
        mx.assign(2 * sz, {{0, 0}, 0});
        mn.assign(2 * sz, {{0, 0}, 0});
        build();
    }

    void build(int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        mx_mod[ind] = INF, mn_mod[ind] = -INF, mod[ind] = 0;
        if (L == R) {
            mx[ind] = {{0, -INF}, 1};
            mn[ind] = {{0, INF}, 1};
            sum[ind] = 0;
            return;
        }
        int M = (L + R) / 2;
        build(2 * ind, L, M); build(2 * ind + 1, M + 1, R);
        pull(ind);
    }

    T comb_mn(T a, T b) {
        if (a > b) 
            std::swap(a, b);
        if (a.first.first == b.first.first) 
            return  {{a.first.first, 
                std::min(a.first.second, b.first.second)}, 
                a.second + b.second};
        return {{a.first.first, std::min(a.first.second, b.first.first)}, a.second};
    }

    T comb_mx(T a, T b) {
        if (a < b) std::swap(a, b);
        if (a.first.first == b.first.first) 
            return  {{a.first.first, 
                std::max(a.first.second, b.first.second)}, 
                a.second + b.second};
        return {{a.first.first, std::max(a.first.second, b.first.first)}, 
            a.second};
    }

    void pull(int ind) {
        sum[ind] = sum[2 * ind] + sum[2 * ind + 1];
        mn[ind] = comb_mn(mn[2 * ind], mn[2 * ind + 1]);
        mx[ind] = comb_mx(mx[2 * ind], mx[2 * ind + 1]);
    }

    void push(int ind, int L, int R) {
        auto chk = [](C& a, C b, C c) {
            if (a == b)
                a = c;
        };
        if (mn_mod[ind] != -INF) {
            if (mn_mod[ind] > mn[ind].first.first) {
                sum[ind] += (mn_mod[ind] - mn[ind].first.first) * mn[ind].second;
                chk(mx[ind].first.first, mn[ind].first.first, mn_mod[ind]);
                chk(mx[ind].first.second, mn[ind].first.first, mn_mod[ind]);
                mn[ind].first.first = mn_mod[ind];
                if (L != R) {
                    for (int i = 0; i < 2; i++) {
                        int pos = 2 * ind + i;
                        mn_mod[pos] = std::max(mn_mod[pos], mn_mod[ind] - mod[pos]);
                        mx_mod[pos] = std::max(mx_mod[pos], mn_mod[pos]);
                    }
                }
            }
            mn_mod[ind] = -INF;
        }
        if (mx_mod[ind] != INF) {
            if (mx_mod[ind] < mx[ind].first.first) {
                sum[ind] += (mx_mod[ind] - mx[ind].first.first) * mx[ind].second;
                chk(mn[ind].first.first, mx[ind].first.first, mx_mod[ind]);
                chk(mn[ind].first.second, mx[ind].first.first, mx_mod[ind]);
                mx[ind].first.first = mx_mod[ind];
                if (L != R) {
                    for (int i = 0; i < 2; i++) {
                        int pos = 2 * ind + i;
                        mx_mod[pos] = std::min(mx_mod[pos], mx_mod[ind] - mod[pos]);
                        mn_mod[pos] = std::min(mn_mod[pos], mx_mod[pos]);
                    }
                }
            }
            mx_mod[ind] = INF;
        }
        if (mod[ind] != 0) {
            sum[ind] += mod[ind] * (R - L + 1);
            auto inc = [&](T& a, C b) {
                if (std::abs(a.first.first) != INF) 
                    a.first.first += b;
                if (std::abs(a.first.second) != INF)
                    a.first.second += b;
            };
            inc(mx[ind], mod[ind]); inc(mn[ind], mod[ind]);
            if (L != R) {
                for (int i = 0; i < 2; i++) {
                    int pos = 2 * ind + i;
                    mod[pos] += mod[ind];
                }
            }
            mod[ind] = 0;
        }
    }

    C qsum(int lo, int hi, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);
        if (R < lo || hi < L)
            return 0;
        if (lo <= L && R <= hi)     
            return sum[ind];
        int M = (L + R) / 2;
        return qsum(lo, hi, 2 * ind, L, M) + qsum(lo, hi, 2 * ind + 1, M + 1, R);
    }

    C qmax(int lo, int hi, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);
        if (R < lo || hi < L)
            return -INF;
        if (lo <= L && R <= hi)     
            return mx[ind].first.first;
        int M = (L + R) / 2;
        return std::max(qmax(lo, hi, 2 * ind, L, M), qmax(lo, hi, 2 * ind + 1, M + 1, R));
    }

    C qmin(int lo, int hi, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);
        if (R < lo || hi < L)
            return INF;
        if (lo <= L && R <= hi)     
            return mn[ind].first.first;
        int M = (L + R) / 2;
        return std::min(qmin(lo, hi, 2 * ind, L, M), qmin(lo, hi, 2 * ind + 1, M + 1, R));
    }
    
    void upd(int t, int lo, int hi, C b, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);
        if (R < lo || hi < L) 
            return;
        if (t == 0) 
            if (b >= mx[ind].first.first)
                return;
        else if (t == 1)
            if (b <= mn[ind].first.first)
                return;
        if (lo <= L && R <= hi) {
            if (t == 0) {
                if (b  > mx[ind].first.second) {
                    mx_mod[ind] = b;
                    push(ind, L, R);
                    return;
                }
            } else if (t == 1) {
                if (b < mn[ind].first.second) {
                    mn_mod[ind] = b;
                    push(ind, L, R);
                    return;
                }
            } else if (t == 2) {
                mod[ind] = b;
                push(ind, L, R);
                return;
            } else assert(false);
        }
        assert(L != R);
        int M = (L + R) / 2;
        upd(t, lo, hi, b, 2 * ind, L, M); upd(t, lo, hi, b, 2 * ind + 1, M + 1, R);
        pull(ind);
    }
};

const ll INF = 1e18;
struct MaxSeg {
    vl lz;
    vector<pair<ll, int>> st;
    int sz;

    void pull(int i) {
        st[i] = max(st[2 * i], st[2 * i + 1]);
    }

    void init(int n) {
        sz = 1;
        while (sz < n) sz <<= 1;
        lz.assign(2 * sz, 0);
        st.resize(2 * sz);
        f0r(i, sz) st[i + sz] = mp(0, i);
        for (int i = sz - 1; i >= 1; i--) pull(i);
    }

    void push(int i, int l, int r) {
        st[i].f += lz[i];
        if (l != r) { 
            lz[2 * i] += lz[i];
            lz[2 * i + 1] += lz[i];
        }
        lz[i] = 0;
    }

    void upd(int lo, int hi, ll inc, int i = 1, int l = 0, int r = -1) {
        if (r == -1) r += sz;
        push(i, l, r);
        if (hi < l || r < lo) return;
        if (lo <= l && r <= hi) {
            lz[i] = inc;
            push(i, l, r);
            return;
        }
        int m = (l + r) >> 1;
        upd(lo, hi, inc, 2 * i, l, m);
        upd(lo, hi, inc, 2 * i + 1, m + 1, r);
        pull(i);
    }

    pair<ll, int> query(int lo, int hi, int i = 1, int l = 0, int r = -1) {
        if (r == -1) r += sz;
        push(i, l, r);
        if (hi < l || r < lo) return mp(-2 * INF, -1);
        if (lo <= l && r <= hi) return st[i];
        int m = (l + r) >> 1;
        return max(query(lo, hi, 2 * i, l, m), query(lo, hi, 2 * i + 1, m + 1, r));
    }
};

vpl queries[N]; 
int ans[N];


int n, m, q;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> q;
    vector<array<ll, 5>> que(q);
    SumSeg sseg; sseg.init(n);
    SegmentTreeBeats<ll> seg; seg.init(n);
    f0r(t, q) { 
        int ty; cin >> ty;
        auto& qq = que[t];
        ty--;
        qq[0] = ty;
        if (ty == 0) {
            int l, r, c; ll k; cin >> l >> r >> c >> k;
            l--, r--;
            qq[1] = l;
            qq[2] = r;
            qq[3] = c;
            qq[4] = k;
            sseg.upd(l, r, k);
            seg.upd(2, l, r, k);
        } else if (ty == 1) { 
            int l, r; ll k; cin >> l >> r >> k;
            l--, r--;
            qq[1] = l;
            qq[2] = r;
            qq[3] = k;
            seg.upd(2, l, r, -k);
            seg.upd(1, l, r, 0);
        } else {
            int a, b; cin >> a >> b;
            a--;
            qq[1] = a;
            ll tt = sseg.query(a, a);
            ll c = seg.qsum(a, a);
            ll amt;
            if (b <= c) amt = tt - (c - b);
            else amt = INF;
            qq[2] = amt;
            queries[a].eb(amt, t);
        }
    }
    f0r(i, n) sort(all(queries[i])), reverse(all(queries[i]));
    MaxSeg mseg; mseg.init(n);
    f0r(i, n) {
        if (queries[i].empty()) {
            mseg.upd(i, i, -2 * INF);
            continue;
        }
        mseg.upd(i, i, -queries[i].back().f);
    }
    f0r(t, q) {
        auto& qq = que[t];
        int ty = qq[0];
        if (ty == 0) { 
            int l = qq[1];
            int r = qq[2];
            int c = qq[3];
            int k = qq[4];
            mseg.upd(l, r, k);
            auto res = mseg.query(0, n - 1);
            while (res.f >= 0) {
                int loc = res.s;
                auto done = queries[loc].back();
                ans[done.s] = c;
                mseg.upd(loc, loc, done.f);
                queries[loc].pop_back();
                if (!queries[loc].empty()) {
                    auto nxt = queries[loc].back();
                    mseg.upd(loc, loc, -nxt.f);
                } else {
                    mseg.upd(loc, loc, -INF);
                }
                res = mseg.query(0, n - 1);
            }
        } else if (ty == 1) {
            continue;
        } else {
            continue;
        }
    }
    f0r(i, q) {
        if (que[i][0] != 2) continue;
        cout << ans[i] << '\n';
    }

    return 0;
}

/** 
 * So basically, we can reindex the person, so we want to find the first point in time you have >= x customers at shop i 
 * 
 */

Compilation message

foodcourt.cpp: In member function 'void SegmentTreeBeats<C>::upd(int, int, int, C, int, int, int)':
foodcourt.cpp:235:12: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
  235 |         if (t == 0)
      |            ^

Subtask #1

2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	12632 KB	Output is correct
2	Correct	14 ms	12536 KB	Output is correct
3	Correct	12 ms	12512 KB	Output is correct
4	Correct	14 ms	12748 KB	Output is correct
5	Correct	8 ms	12108 KB	Output is correct
6	Correct	9 ms	12108 KB	Output is correct
7	Correct	14 ms	12548 KB	Output is correct
8	Correct	14 ms	12620 KB	Output is correct
9	Correct	15 ms	12624 KB	Output is correct
10	Correct	16 ms	12620 KB	Output is correct
11	Correct	14 ms	12588 KB	Output is correct
12	Correct	15 ms	12544 KB	Output is correct
13	Correct	11 ms	12516 KB	Output is correct
14	Correct	11 ms	12620 KB	Output is correct
15	Correct	12 ms	12620 KB	Output is correct
16	Correct	13 ms	12644 KB	Output is correct
17	Correct	14 ms	12620 KB	Output is correct
18	Correct	15 ms	12620 KB	Output is correct
19	Correct	13 ms	12620 KB	Output is correct
20	Correct	16 ms	12644 KB	Output is correct

Subtask #2

0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	12632 KB	Output is correct
2	Correct	14 ms	12536 KB	Output is correct
3	Correct	12 ms	12512 KB	Output is correct
4	Correct	14 ms	12748 KB	Output is correct
5	Correct	8 ms	12108 KB	Output is correct
6	Correct	9 ms	12108 KB	Output is correct
7	Correct	14 ms	12548 KB	Output is correct
8	Correct	14 ms	12620 KB	Output is correct
9	Correct	15 ms	12624 KB	Output is correct
10	Correct	16 ms	12620 KB	Output is correct
11	Correct	14 ms	12588 KB	Output is correct
12	Correct	15 ms	12544 KB	Output is correct
13	Correct	11 ms	12516 KB	Output is correct
14	Correct	11 ms	12620 KB	Output is correct
15	Correct	12 ms	12620 KB	Output is correct
16	Correct	13 ms	12644 KB	Output is correct
17	Correct	14 ms	12620 KB	Output is correct
18	Correct	15 ms	12620 KB	Output is correct
19	Correct	13 ms	12620 KB	Output is correct
20	Correct	16 ms	12644 KB	Output is correct
21	Incorrect	10 ms	12620 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #3

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	343 ms	30668 KB	Output is correct
2	Correct	342 ms	30544 KB	Output is correct
3	Correct	379 ms	30672 KB	Output is correct
4	Correct	339 ms	30840 KB	Output is correct
5	Correct	391 ms	30536 KB	Output is correct
6	Correct	358 ms	30532 KB	Output is correct
7	Correct	32 ms	15084 KB	Output is correct
8	Correct	35 ms	15120 KB	Output is correct
9	Correct	326 ms	30624 KB	Output is correct
10	Correct	357 ms	30584 KB	Output is correct
11	Correct	389 ms	30676 KB	Output is correct
12	Correct	361 ms	30568 KB	Output is correct
13	Correct	334 ms	30492 KB	Output is correct
14	Correct	324 ms	30892 KB	Output is correct
15	Correct	316 ms	30532 KB	Output is correct
16	Correct	344 ms	30668 KB	Output is correct

Subtask #4

0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	214 ms	158400 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #5

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	12632 KB	Output is correct
2	Correct	14 ms	12536 KB	Output is correct
3	Correct	12 ms	12512 KB	Output is correct
4	Correct	14 ms	12748 KB	Output is correct
5	Correct	8 ms	12108 KB	Output is correct
6	Correct	9 ms	12108 KB	Output is correct
7	Correct	14 ms	12548 KB	Output is correct
8	Correct	14 ms	12620 KB	Output is correct
9	Correct	15 ms	12624 KB	Output is correct
10	Correct	16 ms	12620 KB	Output is correct
11	Correct	14 ms	12588 KB	Output is correct
12	Correct	15 ms	12544 KB	Output is correct
13	Correct	11 ms	12516 KB	Output is correct
14	Correct	11 ms	12620 KB	Output is correct
15	Correct	12 ms	12620 KB	Output is correct
16	Correct	13 ms	12644 KB	Output is correct
17	Correct	14 ms	12620 KB	Output is correct
18	Correct	15 ms	12620 KB	Output is correct
19	Correct	13 ms	12620 KB	Output is correct
20	Correct	16 ms	12644 KB	Output is correct
21	Correct	343 ms	30668 KB	Output is correct
22	Correct	342 ms	30544 KB	Output is correct
23	Correct	379 ms	30672 KB	Output is correct
24	Correct	339 ms	30840 KB	Output is correct
25	Correct	391 ms	30536 KB	Output is correct
26	Correct	358 ms	30532 KB	Output is correct
27	Correct	32 ms	15084 KB	Output is correct
28	Correct	35 ms	15120 KB	Output is correct
29	Correct	326 ms	30624 KB	Output is correct
30	Correct	357 ms	30584 KB	Output is correct
31	Correct	389 ms	30676 KB	Output is correct
32	Correct	361 ms	30568 KB	Output is correct
33	Correct	334 ms	30492 KB	Output is correct
34	Correct	324 ms	30892 KB	Output is correct
35	Correct	316 ms	30532 KB	Output is correct
36	Correct	344 ms	30668 KB	Output is correct
37	Correct	353 ms	30684 KB	Output is correct
38	Correct	302 ms	30020 KB	Output is correct
39	Correct	29 ms	14688 KB	Output is correct
40	Correct	34 ms	15068 KB	Output is correct
41	Correct	371 ms	30784 KB	Output is correct
42	Correct	358 ms	30808 KB	Output is correct
43	Correct	419 ms	30760 KB	Output is correct
44	Correct	399 ms	30972 KB	Output is correct
45	Correct	414 ms	30752 KB	Output is correct
46	Correct	416 ms	30772 KB	Output is correct
47	Correct	194 ms	30916 KB	Output is correct
48	Correct	309 ms	30948 KB	Output is correct
49	Correct	337 ms	29768 KB	Output is correct
50	Correct	412 ms	30248 KB	Output is correct
51	Correct	463 ms	30788 KB	Output is correct
52	Correct	511 ms	30660 KB	Output is correct
53	Correct	268 ms	29976 KB	Output is correct
54	Correct	343 ms	30588 KB	Output is correct

Subtask #6

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	92 ms	32100 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	12632 KB	Output is correct
2	Correct	14 ms	12536 KB	Output is correct
3	Correct	12 ms	12512 KB	Output is correct
4	Correct	14 ms	12748 KB	Output is correct
5	Correct	8 ms	12108 KB	Output is correct
6	Correct	9 ms	12108 KB	Output is correct
7	Correct	14 ms	12548 KB	Output is correct
8	Correct	14 ms	12620 KB	Output is correct
9	Correct	15 ms	12624 KB	Output is correct
10	Correct	16 ms	12620 KB	Output is correct
11	Correct	14 ms	12588 KB	Output is correct
12	Correct	15 ms	12544 KB	Output is correct
13	Correct	11 ms	12516 KB	Output is correct
14	Correct	11 ms	12620 KB	Output is correct
15	Correct	12 ms	12620 KB	Output is correct
16	Correct	13 ms	12644 KB	Output is correct
17	Correct	14 ms	12620 KB	Output is correct
18	Correct	15 ms	12620 KB	Output is correct
19	Correct	13 ms	12620 KB	Output is correct
20	Correct	16 ms	12644 KB	Output is correct
21	Incorrect	10 ms	12620 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #8

0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	12632 KB	Output is correct
2	Correct	14 ms	12536 KB	Output is correct
3	Correct	12 ms	12512 KB	Output is correct
4	Correct	14 ms	12748 KB	Output is correct
5	Correct	8 ms	12108 KB	Output is correct
6	Correct	9 ms	12108 KB	Output is correct
7	Correct	14 ms	12548 KB	Output is correct
8	Correct	14 ms	12620 KB	Output is correct
9	Correct	15 ms	12624 KB	Output is correct
10	Correct	16 ms	12620 KB	Output is correct
11	Correct	14 ms	12588 KB	Output is correct
12	Correct	15 ms	12544 KB	Output is correct
13	Correct	11 ms	12516 KB	Output is correct
14	Correct	11 ms	12620 KB	Output is correct
15	Correct	12 ms	12620 KB	Output is correct
16	Correct	13 ms	12644 KB	Output is correct
17	Correct	14 ms	12620 KB	Output is correct
18	Correct	15 ms	12620 KB	Output is correct
19	Correct	13 ms	12620 KB	Output is correct
20	Correct	16 ms	12644 KB	Output is correct
21	Incorrect	10 ms	12620 KB	Output isn't correct
22	Halted	0 ms	0 KB	-