Submission #882273

#	Time	Username	Problem	Language	Result	Execution time	Memory
882273		Regulus	Food Court (JOI21_foodcourt)	C++17	13 / 100	46 ms	19028 KiB

foodcourt

#include <bits/stdc++.h>            // pA
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define debug(x) cerr << #x << " = " << (x) << ' '
#define endl cerr << '\n'
#define all(v) (v).begin(), (v).end()
#define SZ(v) (ll)(v).size()
#define lowbit(x) (x)&-(x)
#define pb emplace_back
#define F first
#define S second
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

const int N = 3e5+5;
//const int INF = 2e9;
ll Q, bit[N], a[N], ans[N];
struct Query {
    ll t, tin, c, k;
    Query() {}
    Query(ll tt, ll tttt, ll cc, ll kk) : t(tt), tin(tttt), c(cc), k(kk) {}
};
vector<Query> v[N];
vector<int> v2;

inline ll query(int x)
{
    ll ret = 0;
    for (int i=x; i > 0; i-=lowbit(i)) ret += bit[i];
    return ret;
}

inline void upd(ll x, ll val)
{
    for (int i=x; i <= Q; i+=lowbit(i)) bit[i] += val;
}

inline bool cmp(Query a, Query b) { return a.tin < b.tin; }

int main(void)
{ IO
    ll n, m, i, t, L, R, c, k, lb, ub, mid;

    cin >> n >> m >> Q;
    for (i=1; i <= Q; ++i)
    {
        cin >> t;
        if (t == 1)
        {
            cin >> L >> R >> c >> k;
            v[L].pb(t, i, c, k);
            v[R+1].pb(-t, i, c, k);
        } else if (t == 2) {
            assert(0);
        } else if (t == 3) {
            cin >> L >> k;
            v[L].pb(t, i, 0, k), v2.pb(i);
        } else while (1);
    }

    for (i=1; i <= n; ++i)
    {
        sort(all(v[i]), cmp);
        for (auto q : v[i])
        {
            if (q.t == 1) upd(q.tin, q.k), a[q.tin] = q.c;
            else if (q.t == -1) upd(q.tin, -q.k), a[q.tin] = 0;
            else {
                lb = 1, ub = q.tin;
                while (lb < ub)
                {
                    mid = (lb+ub)>>1;
                    if (query(mid) >= q.k) ub = mid;
                    else lb = mid + 1;
                }
                if (lb == q.tin) ans[q.tin] = 0;
                else if (a[lb] == 0) assert(0);
                else ans[q.tin] = a[lb];
            }
        }
    }

    for (int x : v2) cout << ans[x] << '\n';

    return 0;
}

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