oj.uz

Submission #540126

# Submission time Handle Problem Language Result Execution time Memory
540126 2022-03-19T09:57:49 Z LittleCube Food Court (JOI21_foodcourt) C++14
13 / 100
 78 ms 8120 KB 
#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;

ll 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)
        {
            int t = bsearch(queries[qdx].S.S);
            if (t > queries[qdx].S.F)
                ans[queries[qdx].S.F] = 0;
            else
                ans[queries[qdx].S.F] = color[t];
            qdx++;
        }
    }
    for (int i = 1; i <= Q; i++)
        if (ans[i] >= 0)
            cout << ans[i] << '\n';
}

/*
3 4 7
3 1 1000000000
1 1 3 1 5000000000
1 1 2 4 5000000000
3 2 5000000001
1 1 3 3 5000000000
3 3 10000000000
3 1 15000000000
*/

Compilation message

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:75: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]
   75 |         while (mdx < modifies.size() && modifies[mdx].F == i)
      |                ~~~~^~~~~~~~~~~~~~~~~
foodcourt.cpp:80: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]
   80 |         while (qdx < queries.size() && queries[qdx].F == i)
      |                ~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 5604 KB Output is correct
2 Correct 77 ms 7736 KB Output is correct
3 Correct 78 ms 8080 KB Output is correct
4 Correct 40 ms 6468 KB Output is correct
5 Correct 50 ms 6872 KB Output is correct
6 Correct 56 ms 7632 KB Output is correct
7 Correct 34 ms 6568 KB Output is correct
8 Correct 37 ms 6364 KB Output is correct
9 Correct 50 ms 7396 KB Output is correct
10 Correct 41 ms 6500 KB Output is correct
11 Correct 61 ms 7448 KB Output is correct
12 Correct 61 ms 8120 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -