Submission #540123

#	Time	Username	Problem	Language	Result	Execution time	Memory
540123		LittleCube	Food Court (JOI21_foodcourt)	C++14	0 / 100	46 ms	5584 KiB

foodcourt

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int N, M, Q, seg[300005], lazy[300005], ans[300005], color[300005];
vector<pair<int, pair<int, pll>>> modifies, colors;
vector<pair<int, pll>> queries;

void modify(int mL, int mR, ll val, int i = 1, int L = 1, int R = Q + 1)
{
    if (mL <= L && R <= mR)
        lazy[i] += val;
    else if (R < mL || mR < L)
        return;
    else
    {
        int mid = (L + R) / 2;
        lazy[i * 2] += lazy[i];
        lazy[i * 2 + 1] += lazy[i];
        lazy[i] = 0;
        modify(mL, mR, val, i * 2, L, mid);
        modify(mL, mR, val, i * 2 + 1, mid + 1, R);
        seg[i] = seg[i * 2 + 1] + lazy[i * 2 + 1];
    }
}


int bsearch(ll val, int i = 1, int L = 1, int R = Q + 1)
{
    if (L == R)
        return L;
    else
    {
        lazy[i * 2] += lazy[i];
        lazy[i * 2 + 1] += lazy[i];
        seg[i] += lazy[i];
        lazy[i] = 0;
        int mid = (L + R) / 2;
        if (seg[i * 2] + lazy[i * 2] >= val)
            return bsearch(val, i * 2, L, mid);
        else
            return bsearch(val, i * 2 + 1, mid + 1, R);
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M >> Q;
    for (int i = 1; i <= Q; i++)
    {
        ll T, L, R, C, K;
        cin >> T >> L >> R;
        assert(T != 2);
        if (T == 1)
        {
            cin >> C >> K;
            modifies.emplace_back(pair<int, pair<int, pll>>{L, {i, {C, K}}});
            modifies.emplace_back(pair<int, pair<int, pll>>{R + 1, {i, {-C, -K}}});
            color[i] = C;
            ans[i] = -1;
        }
        else
            queries.emplace_back(pair<int, pll>{L, {i, R}});
    }
    sort(modifies.begin(), modifies.end());
    sort(queries.begin(), queries.end());
    int mdx = 0, qdx = 0;
    for (int i = 1; i <= N; i++)
    {

        while (mdx < modifies.size() && modifies[mdx].F == i)
        {
            modify(modifies[mdx].S.F, Q + 1, modifies[mdx].S.S.S);
            mdx++;
        }
        while (qdx < queries.size() && queries[qdx].F == i)
        {
            ans[queries[qdx].S.F] = color[bsearch(queries[qdx].S.S)];
            qdx++;
        }
    }
    for (int i = 1; i <= Q; i++)
        if (ans[i] >= 0)
            cout << ans[i] << '\n';
}


/*
3 4 5
1 2 3 1 50
1 1 2 4 50
3 2 51
1 1 1 3 50
3 1 100
*/

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, std::pair<long long int, long long int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         while (mdx < modifies.size() && modifies[mdx].F == i)
      |                ~~~~^~~~~~~~~~~~~~~~~
foodcourt.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         while (qdx < queries.size() && queries[qdx].F == i)
      |                ~~~~^~~~~~~~~~~~~~~~

• 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