oj.uz

답안 #396436

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
396436 2021-04-30T00:31:34 Z 12tqian 푸드 코트 (JOI21_foodcourt) C++17
24 / 100
 473 ms 141820 KB 
#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 = 2.5e5 + 5;


int n, m, q; 

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 main() {
    // freopen("input.in", "r", stdin);
    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, 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, 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:236:12: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
  236 |         if (t == 0)
      |            ^

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 6732 KB Output is correct
2 Correct 11 ms 6672 KB Output is correct
3 Correct 9 ms 6732 KB Output is correct
4 Correct 10 ms 6732 KB Output is correct
5 Correct 5 ms 6220 KB Output is correct
6 Correct 5 ms 6220 KB Output is correct
7 Correct 10 ms 6668 KB Output is correct
8 Correct 10 ms 6732 KB Output is correct
9 Correct 11 ms 6732 KB Output is correct
10 Correct 10 ms 6732 KB Output is correct
11 Correct 10 ms 6660 KB Output is correct
12 Correct 11 ms 6660 KB Output is correct
13 Correct 7 ms 6732 KB Output is correct
14 Correct 8 ms 6732 KB Output is correct
15 Correct 8 ms 6732 KB Output is correct
16 Correct 9 ms 6732 KB Output is correct
17 Correct 10 ms 6768 KB Output is correct
18 Correct 11 ms 6732 KB Output is correct
19 Correct 9 ms 6732 KB Output is correct
20 Correct 10 ms 6764 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 6732 KB Output is correct
2 Correct 11 ms 6672 KB Output is correct
3 Correct 9 ms 6732 KB Output is correct
4 Correct 10 ms 6732 KB Output is correct
5 Correct 5 ms 6220 KB Output is correct
6 Correct 5 ms 6220 KB Output is correct
7 Correct 10 ms 6668 KB Output is correct
8 Correct 10 ms 6732 KB Output is correct
9 Correct 11 ms 6732 KB Output is correct
10 Correct 10 ms 6732 KB Output is correct
11 Correct 10 ms 6660 KB Output is correct
12 Correct 11 ms 6660 KB Output is correct
13 Correct 7 ms 6732 KB Output is correct
14 Correct 8 ms 6732 KB Output is correct
15 Correct 8 ms 6732 KB Output is correct
16 Correct 9 ms 6732 KB Output is correct
17 Correct 10 ms 6768 KB Output is correct
18 Correct 11 ms 6732 KB Output is correct
19 Correct 9 ms 6732 KB Output is correct
20 Correct 10 ms 6764 KB Output is correct
21 Incorrect 5 ms 6732 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 328 ms 24796 KB Output is correct
2 Correct 350 ms 24692 KB Output is correct
3 Correct 346 ms 24856 KB Output is correct
4 Correct 340 ms 24904 KB Output is correct
5 Correct 355 ms 24764 KB Output is correct
6 Correct 361 ms 24644 KB Output is correct
7 Correct 29 ms 9248 KB Output is correct
8 Correct 32 ms 9356 KB Output is correct
9 Correct 322 ms 24932 KB Output is correct
10 Correct 338 ms 24644 KB Output is correct
11 Correct 333 ms 24860 KB Output is correct
12 Correct 339 ms 24720 KB Output is correct
13 Correct 262 ms 24720 KB Output is correct
14 Correct 314 ms 25028 KB Output is correct
15 Correct 302 ms 24604 KB Output is correct
16 Correct 341 ms 24604 KB Output is correct

Subtask #4
0 / 21.0

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

Subtask #5
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 6732 KB Output is correct
2 Correct 11 ms 6672 KB Output is correct
3 Correct 9 ms 6732 KB Output is correct
4 Correct 10 ms 6732 KB Output is correct
5 Correct 5 ms 6220 KB Output is correct
6 Correct 5 ms 6220 KB Output is correct
7 Correct 10 ms 6668 KB Output is correct
8 Correct 10 ms 6732 KB Output is correct
9 Correct 11 ms 6732 KB Output is correct
10 Correct 10 ms 6732 KB Output is correct
11 Correct 10 ms 6660 KB Output is correct
12 Correct 11 ms 6660 KB Output is correct
13 Correct 7 ms 6732 KB Output is correct
14 Correct 8 ms 6732 KB Output is correct
15 Correct 8 ms 6732 KB Output is correct
16 Correct 9 ms 6732 KB Output is correct
17 Correct 10 ms 6768 KB Output is correct
18 Correct 11 ms 6732 KB Output is correct
19 Correct 9 ms 6732 KB Output is correct
20 Correct 10 ms 6764 KB Output is correct
21 Correct 328 ms 24796 KB Output is correct
22 Correct 350 ms 24692 KB Output is correct
23 Correct 346 ms 24856 KB Output is correct
24 Correct 340 ms 24904 KB Output is correct
25 Correct 355 ms 24764 KB Output is correct
26 Correct 361 ms 24644 KB Output is correct
27 Correct 29 ms 9248 KB Output is correct
28 Correct 32 ms 9356 KB Output is correct
29 Correct 322 ms 24932 KB Output is correct
30 Correct 338 ms 24644 KB Output is correct
31 Correct 333 ms 24860 KB Output is correct
32 Correct 339 ms 24720 KB Output is correct
33 Correct 262 ms 24720 KB Output is correct
34 Correct 314 ms 25028 KB Output is correct
35 Correct 302 ms 24604 KB Output is correct
36 Correct 341 ms 24604 KB Output is correct
37 Correct 355 ms 24772 KB Output is correct
38 Correct 291 ms 24280 KB Output is correct
39 Correct 25 ms 8848 KB Output is correct
40 Correct 30 ms 9152 KB Output is correct
41 Correct 358 ms 25084 KB Output is correct
42 Correct 356 ms 24924 KB Output is correct
43 Correct 404 ms 24904 KB Output is correct
44 Correct 385 ms 25000 KB Output is correct
45 Correct 364 ms 25048 KB Output is correct
46 Correct 401 ms 25028 KB Output is correct
47 Correct 191 ms 25156 KB Output is correct
48 Correct 299 ms 25080 KB Output is correct
49 Correct 315 ms 23904 KB Output is correct
50 Correct 403 ms 24304 KB Output is correct
51 Correct 462 ms 24788 KB Output is correct
52 Correct 473 ms 24772 KB Output is correct
53 Correct 269 ms 24008 KB Output is correct
54 Correct 336 ms 24680 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 6732 KB Output is correct
2 Correct 11 ms 6672 KB Output is correct
3 Correct 9 ms 6732 KB Output is correct
4 Correct 10 ms 6732 KB Output is correct
5 Correct 5 ms 6220 KB Output is correct
6 Correct 5 ms 6220 KB Output is correct
7 Correct 10 ms 6668 KB Output is correct
8 Correct 10 ms 6732 KB Output is correct
9 Correct 11 ms 6732 KB Output is correct
10 Correct 10 ms 6732 KB Output is correct
11 Correct 10 ms 6660 KB Output is correct
12 Correct 11 ms 6660 KB Output is correct
13 Correct 7 ms 6732 KB Output is correct
14 Correct 8 ms 6732 KB Output is correct
15 Correct 8 ms 6732 KB Output is correct
16 Correct 9 ms 6732 KB Output is correct
17 Correct 10 ms 6768 KB Output is correct
18 Correct 11 ms 6732 KB Output is correct
19 Correct 9 ms 6732 KB Output is correct
20 Correct 10 ms 6764 KB Output is correct
21 Incorrect 5 ms 6732 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 6732 KB Output is correct
2 Correct 11 ms 6672 KB Output is correct
3 Correct 9 ms 6732 KB Output is correct
4 Correct 10 ms 6732 KB Output is correct
5 Correct 5 ms 6220 KB Output is correct
6 Correct 5 ms 6220 KB Output is correct
7 Correct 10 ms 6668 KB Output is correct
8 Correct 10 ms 6732 KB Output is correct
9 Correct 11 ms 6732 KB Output is correct
10 Correct 10 ms 6732 KB Output is correct
11 Correct 10 ms 6660 KB Output is correct
12 Correct 11 ms 6660 KB Output is correct
13 Correct 7 ms 6732 KB Output is correct
14 Correct 8 ms 6732 KB Output is correct
15 Correct 8 ms 6732 KB Output is correct
16 Correct 9 ms 6732 KB Output is correct
17 Correct 10 ms 6768 KB Output is correct
18 Correct 11 ms 6732 KB Output is correct
19 Correct 9 ms 6732 KB Output is correct
20 Correct 10 ms 6764 KB Output is correct
21 Incorrect 5 ms 6732 KB Output isn't correct
22 Halted 0 ms 0 KB -