제출 #742885

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
742885		GrindMachine	푸드 코트 (JOI21_foodcourt)	C++17	100 / 100	450 ms	41400 KiB

foodcourt

// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
https://codeforces.com/blog/entry/88748?#comment-772940
https://oj.uz/submission/741888

key idea:
sweep over shops instead of queries

when we are at a given shop, we can maintain all active queries in a segtree
op 1 = +k, op2 = -k

process all queries on this shop
let the query have ind = id

the #of people at the shop during the time of the query
= max suff sum ending at id

can be calculated with segtree

tot_guys = tot #of guys who have entered shop i until time = id (including people who have left)
curr_guys = current #of people in the shop
we want to find the group num of the vth guy in the guys currently at the shop

we will find the query id where (tot_guys-curr_guys+v)th guy amongst all guys who have entered the shop (and left)
can be done with b.s + segtree

once the query id is found, the group num can also be found
group num of this guy = group num of this query id

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct segtree {
    // https://codeforces.com/blog/entry/18051

    /*=======================================================*/

    struct data {
        ll mxsuff, sum, plus_sum;
    };

    data neutral = {0, 0, 0};

    data merge(data &left, data &right) {
        data curr;

        curr.mxsuff = max(right.mxsuff, right.sum + left.mxsuff);
        curr.sum = left.sum + right.sum;
        curr.plus_sum = left.plus_sum + right.plus_sum;

        return curr;
    }

    void create(int i, T v) {

    }

    void modify(int i, T v) {
        tr[i].sum = v;
        tr[i].mxsuff = max(v, 0ll);
        tr[i].plus_sum = max(v, 0ll);
    }

    /*=======================================================*/

    int n;
    vector<data> tr;

    segtree() {

    }

    segtree(int siz) {
        init(siz);
    }

    void init(int siz) {
        n = siz;
        tr.assign(2 * n, neutral);
    }

    void build(vector<T> &a, int siz) {
        rep(i, siz) create(i + n, a[i]);
        rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    void pupd(int i, T v) {
        modify(i + n, v);
        for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    data query(int l, int r) {
        data resl = neutral, resr = neutral;

        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) resl = merge(resl, tr[l++]);
            if (!(r & 1)) resr = merge(tr[r--], resr);
        }

        return merge(resl, resr);
    }
};

void solve(int test_case)
{
    ll n, m, q; cin >> n >> m >> q;
    vector<ll> group(q + 5);

    vector<pll> upds[n + 5], queries[n + 5];

    rep1(i, q) {
        ll t; cin >> t;
        if (t == 1) {
            ll l, r, c, k; cin >> l >> r >> c >> k;
            group[i] = c;
            upds[l].pb({i, k});
            upds[r + 1].pb({i, 0});
        }
        else if (t == 2) {
            ll l, r, k; cin >> l >> r >> k;
            upds[l].pb({i, -k});
            upds[r + 1].pb({i, 0});
        }
        else {
            ll x, y; cin >> x >> y;
            queries[x].pb({y, i});
        }
    }

    vector<ll> ans(q + 5, -1);
    segtree<ll> st(q + 5);

    rep1(i, n) {
        for (auto [ind, val] : upds[i]) {
            st.pupd(ind, val);
        }

        for (auto [v, id] : queries[i]) {
            auto [mxsuff, sum, plus_sum] = st.query(1, id);
            ll curr_guys = mxsuff;
            ll tot_guys = plus_sum;
            if (v > curr_guys) {
                ans[id] = 0;
            }
            else {
                ll want = tot_guys - curr_guys + v;
                ll l = 1, r = id;
                ll first = -1;
                while (l <= r) {
                    ll mid = (l + r) >> 1;
                    if (st.query(1, mid).plus_sum >= want) {
                        first = mid;
                        r = mid - 1;
                    }
                    else {
                        l = mid + 1;
                    }
                }

                assert(first != -1);
                ans[id] = group[first];
            }
        }
    }

    rep1(i, q) {
        if (ans[i] != -1) {
            cout << ans[i] << endl;
        }
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

• 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