Submission #1099976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099976		cpptowin	Food Court (JOI21_foodcourt)	C++17	0 / 100	406 ms	117332 KiB

foodcourt

#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define bitcount(x) __builtin_popcountll(x)
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define ss(x) (int)x.size()
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
template <class T>
struct Fenwick_Tree
{
    vector<T> bit_add, bit_sub;
    int n;

    Fenwick_Tree(int n = 0) : n(n), bit_add(n + 1), bit_sub(n + 1) {}

    void clear()
    {
        fill(bit_add.begin(), bit_add.end(), T(0));
        fill(bit_sub.begin(), bit_sub.end(), T(0));
    }

    void update(int u, int v, T val)
    {
        for (int i = u; i <= n; i += i & -i)
        {
            bit_add[i] += val;
            bit_sub[i] += 1LL * (u - 1) * val;
        }
        for (int i = v; i <= n; i += i & -i)
        {
            bit_add[i] -= val;
            bit_sub[i] -= 1LL * v * val;
        }
    }

    void update(int u, T val) { update(u, u, val); }

    T get(int u)
    {
        T ans1 = 0, ans2 = 0;
        for (int i = u; i; i -= i & -i)
        {
            ans1 += bit_add[i];
            ans2 += bit_sub[i];
        }
        return u * ans1 - ans2;
    }

    T get(int l, int r) { return get(r) - get(l - 1); }
};
struct SegmentTree
{
    vector<int> st, lazy;
    int n;
    /// real n
    SegmentTree(int _n = 0) : n(_n)
    {
        st.resize(4 * n + 10);
        lazy.resize(4 * n + 10);
    }
    void resize(int _n)
    {
        n = _n;
        st.resize(4 * n + 10);
        lazy.resize(4 * n + 10);
    }
    void down(int id, int l, int r)
    {
        if (lazy[id] == 0)
            return;
        int mid = l + r >> 1;
        st[id << 1] += lazy[id] * (mid - l + 1);
        lazy[id << 1] += lazy[id];
        st[id << 1 | 1] += lazy[id] * (r - mid);
        lazy[id << 1 | 1] += lazy[id];
        lazy[id] = 0;
    }

    void update(int id, int l, int r, int u, int v, int val)
    {
        if (u > r || l > v)
            return;
        if (u <= l && r <= v)
        {
            st[id] += val * (r - l + 1);
            lazy[id] += val;
            return;
        }
        down(id, l, r);
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }
    int get(int id, int l, int r, int u, int v)
    {
        if (l > v || u > r)
            return 0;
        if (u <= l && r <= v)
            return st[id];
        down(id, l, r);
        int mid = (l + r) >> 1;
        return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
    }
    int walkright(int id, int l, int r, int x, int val)
    {
        if (st[id] < val)
            return -1;
        if (r < x)
            return -1;
        if (l == r)
            return l;
        down(id, l, r);
        int mid = l + r >> 1;
        int ans = -1;
        if (st[id << 1] >= val)
            return walkright(id << 1, l, mid, x, val);
        return walkright(id << 1 | 1, mid + 1, r, x, val - st[id << 1]);
    }
    int walkleft(int id, int l, int r, int x, int val)
    {
        if (st[id] < val)
            return -1;
        if (l > x)
            return -1;
        if (l == r)
            return l;
        down(id, l, r);
        int mid = l + r >> 1;
        int ans = -1;
        if (st[id << 1 | 1] >= val)
            return walkleft(id << 1 | 1, mid + 1, r, x, val);
        return walkleft(id << 1, l, mid, x, val - st[id << 1 | 1]);
    }
    int get(int l, int r)
    {
        return get(1, 1, n, l, r);
    }
    void update(int l, int r, int val)
    {
        update(1, 1, n, l, r, val);
    }
    int walkright(int x, int val)
    {
        return walkright(1, 1, n, x, val);
    }
    int walkleft(int x, int val)
    {
        return walkleft(1, 1, n, x, val);
    }
} add;
int lazy[4 * maxn];
pii st[4 * maxn];
void build(int id, int l, int r)
{
    if (l == r)
    {
        st[id] = {0, 1};
        return;
    }
    int mid = l + r >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    st[id].fi = min(st[id << 1].fi, st[id << 1 | 1].fi);
    st[id].se = st[id << 1].se + st[id << 1 | 1].se;
}
void down(int id, int l, int r)
{
    st[id << 1].fi += lazy[id];
    lazy[id << 1] += lazy[id];
    st[id << 1 | 1].fi += lazy[id];
    lazy[id << 1 | 1] += lazy[id];
    lazy[id] = 0;
}

void update(int id, int l, int r, int u, int v, int val)
{
    if (u > r || l > v)
        return;
    if (u <= l && r <= v)
    {
        st[id].fi += val;
        lazy[id] += val;
        return;
    }
    down(id, l, r);
    int mid = (l + r) >> 1;
    update(id << 1, l, mid, u, v, val);
    update(id << 1 | 1, mid + 1, r, u, v, val);
    st[id] = min(st[id << 1], st[id << 1 | 1]);
}

pii get(int id, int l, int r, int u, int v)
{
    if (l > v || u > r)
        return {inf, inf};
    if (u <= l && r <= v)
        return st[id];
    down(id, l, r);
    int mid = (l + r) >> 1;
    return min(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
int n, m, q;
int g[maxn];
vector<array<int, 3>> up[maxn];
bool ok[maxn];
vii qry[maxn];
Fenwick_Tree<int> del(maxn);
int ans[maxn];
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> q;
    add.resize(q + 1);
    fo(i, 1, q)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            int l, r, c, k;
            cin >> l >> r >> c >> k;
            up[l].push_back({k, i, 1});
            up[r + 1].push_back({-k, i, 1});
        }
        else if (t == 2)
        {
            int l, r, k;
            cin >> l >> r >> k;
            up[l].push_back({-k, i, 2});
            up[r + 1].push_back({k, i, 2});
        }
        else
        {
            ok[i] = 1;
            int j, v;
            cin >> j >> v;
            qry[j].pb(v, i);
        }
    }
    build(1, 1, q);
    fo(i, 1, n)
    {
        for (auto [val, pos, t] : up[i])
        {
            update(1, 1, q, pos, q, val);
            if (t == 1)
                add.update(pos, q, val);
            else
                add.update(pos, q, -val);
        }
        int val = 0;
        for (auto [val, pos] : qry[i])
        {
            auto [u, l] = min(get(1, 1, q, 1, pos), {0, 0});
            if (get(1, 1, q, pos, pos).fi < u + val)
                continue;
            val += del.get(pos, pos);
            ans[pos] = add.walkright(l, val);
        }
    }
    fo(i, 1, q) if (ok[i]) cout << ans[i] << "\n";
}

Compilation message (stderr)

foodcourt.cpp: In member function 'void SegmentTree::down(long long int, long long int, long long int)':
foodcourt.cpp:108:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'long long int SegmentTree::walkright(long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:151:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  151 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp:152:13: warning: unused variable 'ans' [-Wunused-variable]
  152 |         int ans = -1;
      |             ^~~
foodcourt.cpp: In member function 'long long int SegmentTree::walkleft(long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:166:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  166 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp:167:13: warning: unused variable 'ans' [-Wunused-variable]
  167 |         int ans = -1;
      |             ^~~
foodcourt.cpp: In function 'void build(long long int, long long int, long long int)':
foodcourt.cpp:198:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  198 |     int mid = l + r >> 1;
      |               ~~^~~
foodcourt.cpp: At global scope:
foodcourt.cpp:247:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  247 | main()
      | ^~~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:296:13: warning: unused variable 'val' [-Wunused-variable]
  296 |         int val = 0;
      |             ^~~
foodcourt.cpp: In instantiation of 'Fenwick_Tree<T>::Fenwick_Tree(long long int) [with T = long long int]':
foodcourt.cpp:245:27:   required from here
foodcourt.cpp:49:9: warning: 'Fenwick_Tree<long long int>::n' will be initialized after [-Wreorder]
   49 |     int n;
      |         ^
foodcourt.cpp:48:15: warning:   'std::vector<long long int> Fenwick_Tree<long long int>::bit_add' [-Wreorder]
   48 |     vector<T> bit_add, bit_sub;
      |               ^~~~~~~
foodcourt.cpp:51:5: warning:   when initialized here [-Wreorder]
   51 |     Fenwick_Tree(int n = 0) : n(n), bit_add(n + 1), bit_sub(n + 1) {}
      |     ^~~~~~~~~~~~
foodcourt.cpp:252:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  252 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:253:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  253 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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