Submission #764343

#	Time	Username	Problem	Language	Result	Execution time	Memory
764343		anhduc2701	Food Court (JOI21_foodcourt)	C++17	100 / 100	587 ms	237400 KiB

foodcourt

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, m, q;
vector<pair<int, int>> d[maxn];
int pref[maxn];
vector<pair<int, int>> G[maxn];

struct seg
{
    pair<int, int> st[maxn * 4];
    int lazy[maxn * 4];
    int st1[maxn * 4];
    void push(int id)
    {
        st[id * 2].fi += lazy[id];
        st[id * 2 + 1].fi += lazy[id];
        lazy[id * 2] += lazy[id];
        lazy[id * 2 + 1] += lazy[id];
        lazy[id] = 0;
    }
    void build(int id, int l, int r)
    {
        st1[id] = 0;
        if (l == r)
        {
            st[id].se = l;
            return;
        }
        int mid = (l + r) / 2;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
        st[id] = min(st[id * 2], st[id * 2 + 1]);
    }
    void update(int id, int l, int r, int u, int v, int val)
    {
        if (r < u || v < l)
        {
            return;
        }
        if (u <= l && r <= v)
        {
            st[id].fi += val;
            lazy[id] += val;
            return;
        }
        int mid = (l + r) / 2;
        push(id);
        update(id * 2, l, mid, u, v, val);
        update(id * 2 + 1, mid + 1, r, u, v, val);
        st[id] = min(st[id * 2], st[id * 2 + 1]);
    }
    pair<int, int> get(int id, int l, int r, int u, int v)
    {
        if (r < u || v < l)
        {
            return {INF, 0};
        }
        if (u <= l && r <= v)
        {
            return st[id];
        }
        int mid = (l + r) / 2;
        push(id);
        return min(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
    }
    void push1(int id)
    {
        st1[id * 2] += lazy[id];
        st1[id * 2 + 1] += lazy[id];
        lazy[id * 2] += lazy[id];
        lazy[id * 2 + 1] += lazy[id];
        lazy[id] = 0;
    }
    void upd(int id, int l, int r, int u, int v, int val)
    {
        if (r < u || v < l)
        {
            return;
        }
        if (u <= l && r <= v)
        {
            st1[id] += val;
            lazy[id] += val;
            return;
        }
        int mid = (l + r) / 2;
        push1(id);
        upd(id * 2, l, mid, u, v, val);
        upd(id * 2 + 1, mid + 1, r, u, v, val);
        st1[id] = max(st1[id * 2], st1[id * 2 + 1]);
    }
    int getval(int id, int l, int r, int u)
    {
        if (l == r)
        {
            return st1[id];
        }
        int mid = (l + r) / 2;
        push1(id);
        if (u <= mid)
        {
            return getval(id * 2, l, mid, u);
        }
        else
            return getval(id * 2 + 1, mid + 1, r, u);
    }
    int get1(int id, int l, int r, int u, int val, int p)
    {
        if (r < u || val > st1[id] - p)
        {
            return -1;
        }
        int mid = (l + r) / 2;
        if (l == r)
        {
            return l;
        }
        push1(id);
        int x = get1(id * 2, l, mid, u, val, p);

        if (x != -1)
        {
            return x;
        }
        return get1(id * 2 + 1, mid + 1, r, u, val, p);
    }
} A, B;
int bit[maxn];
void upd(int id, int val)
{
    for (id; id <= q; id += id & (-id))
    {
        bit[id] += val;
    }
}
int get(int id)
{
    int res = 0;
    for (id; id >= 1; id -= id & (-id))
    {
        res += bit[id];
    }
    return res;
}
vector<pair<int, int>> era[maxn];
int pref1[maxn];
int que[maxn];
int ans[maxn];
signed main()
{
    cin.tie(0), cout.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= q; i++)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            int l, r, c, k;
            cin >> l >> r >> c >> k;
            que[i] = c;
            d[l].pb({i, k});
            d[r + 1].pb({i, -k});
        }
        else if (t == 2)
        {
            int l, r, k;
            cin >> l >> r >> k;
            era[l].pb({i, k});
            era[r + 1].pb({i, -k});
        }
        else if (t == 3)
        {
            int a, b;
            cin >> a >> b;
            G[a].pb({i, b});
        }
        ans[i] = -1;
    }
    A.build(1, 0, q);
    B.build(1, 0, q);
    for (int i = 1; i <= n; i++)
    {
        for (auto v : d[i])
        {
            A.update(1, 0, q, v.fi, q, v.se);
            B.upd(1, 0, q, v.fi, q, v.se);
        }
        for (auto v : era[i])
        {
            A.update(1, 0, q, v.fi, q, -v.se);
            upd(v.fi, v.se);
        }
        for (auto v : G[i])
        {
            pair<int, int> s = A.get(1, 0, q, 0, v.fi);

            int k = B.getval(1, 0, q, s.se);

            int num_era = get(v.fi) - get(s.se);
            int d = B.get1(1, 0, q, s.se, num_era + v.se, k);
            if (d >= v.fi)
            {
                ans[v.fi] = 0;
            }
            else
            {
                ans[v.fi] = que[d];
            }
        }
    }
    for (int i = 1; i <= q; i++)
    {
        if (ans[i] == -1)
            continue;
        cout << ans[i] << "\n";
    }
}

Compilation message (stderr)

foodcourt.cpp: In function 'void upd(long long int, long long int)':
foodcourt.cpp:162:10: warning: statement has no effect [-Wunused-value]
  162 |     for (id; id <= q; id += id & (-id))
      |          ^~
foodcourt.cpp: In function 'long long int get(long long int)':
foodcourt.cpp:170:10: warning: statement has no effect [-Wunused-value]
  170 |     for (id; id >= 1; id -= id & (-id))
      |          ^~

• 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