oj.uz

Submission #930795

# Submission time Handle Problem Language Result Execution time Memory
930795 2024-02-20T12:29:36 Z boris_mihov Food Court (JOI21_foodcourt) C++17
13 / 100
 1000 ms 76512 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 250000 + 10;
const llong INF = 1e18;

int n, m, q;
struct SegmentTree
{
    struct Node
    {
        llong minPrefix;
        llong maxSuffix;
        llong sumPositive;
        llong sumNegative;
        llong sum;
        int c;

        Node()
        {
            maxSuffix = minPrefix = sumPositive = sumNegative = sum = c = 0;
        }   

        friend Node operator + (const Node &left, const Node &right)
        {
            Node res;
            res.sum = left.sum + right.sum;
            res.sumPositive = left.sumPositive + right.sumPositive;
            res.sumNegative = left.sumNegative + right.sumNegative;
            res.minPrefix = std::min(left.minPrefix, left.sum + right.minPrefix);
            res.maxSuffix = std::max(right.maxSuffix, right.sum + left.maxSuffix);
            res.c = std::max(left.c, right.c);
            return res;
        }
    };

    Node tree[4*MAXN];
    void update(int l, int r, int node, int queryPos, int queryVal, int queryC, bool queryType)
    {
        if (l == r)
        {
            tree[node].c = queryC;
            if (queryType == true)
            {
                tree[node].sum = queryVal;
                tree[node].sumNegative = 0;
                tree[node].sumPositive = queryVal;
            } else
            {
                tree[node].sum = -queryVal;
                tree[node].sumPositive = 0;
                tree[node].sumNegative = queryVal;
            }

            tree[node].minPrefix = tree[node].sum;
            tree[node].maxSuffix = tree[node].sum;
            return;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryVal, queryC, queryType);
        else update(mid + 1, r, 2*node + 1, queryPos, queryVal, queryC, queryType);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }

    Node query(int l, int r, int node, int queryL, int queryR)
    {
        if (queryL <= l && r <= queryR)
        {
            return tree[node];
        }

        Node res;
        int mid = (l + r) / 2;
        if (queryL <= mid) res = res + query(l, mid, 2*node, queryL, queryR);
        if (mid + 1 <= queryR) res = res + query(mid + 1, r, 2*node + 1, queryL, queryR);
        return res;
    }

    llong find(int l, int r, int node, int queryL, int queryR, llong k)
    {
        std::cout << "find: " << l << ' ' << r << ' ' << node << ' ' << tree[node].sumPositive << ' ' << k << '\n';
        if (queryR < l || r < queryL)
        {
            return 0;
        }

        if (queryL <= l && r <= queryR && tree[node].sumPositive < k)
        {
            return -tree[node].sumPositive;
        }

        if (l == r)
        {
            return tree[node].c;
        }

        int mid = (l + r) / 2;
        llong res = find(l, mid, 2*node, queryL, queryR, k);
        if (res > 0) return res;
        llong res2 = find(mid + 1, r, 2*node + 1, queryL, queryR, k + res);
        if (res2 > 0) return res2;
        else return res + res2;
    }

    void update(int pos, int val, int c, bool type)
    {
        update(1, q, 1, pos, val, c, type);
    }

    Node query(int l, int r)
    {
        return query(1, q, 1, l, r);
    }

    int find(int l, int r, llong k)
    {
        return find(1, q, 1, l, r, k);
    }
};

struct QueryAsk
{
    int time;
    llong val;
    int idx;
};

struct QueryAdd
{
    bool type;
    int val;
    int c;
    int idx;
};

int cntServices;
std::vector <QueryAdd> activate[MAXN];
std::vector <QueryAdd> deactivate[MAXN];
std::vector <QueryAsk> v[MAXN];
SegmentTree tree;
int answer[MAXN];

void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        for (const QueryAdd query : activate[i])
        {
            tree.update(query.idx, query.val, query.c, query.type);
        }

        for (const QueryAdd query : deactivate[i])
        {
            tree.update(query.idx, 0, 0, false);
        }

        for (const auto &[time, val, idx] : v[i])
        {
            int l = 0, r = time + 1, mid;
            while (l < r - 1)
            {
                mid = (l + r) / 2;
                llong res = tree.query(mid, time).minPrefix;
                if (mid > 1) res += tree.query(1, mid - 1).maxSuffix;
                if (res >= 0) r = mid;
                else l = mid;
            }
            // for (int idx = 1 ; idx <= time ; ++idx)
            // {
            //     if (tree.query(idx, time).minPrefix >= 0)
            //     {
            //         r = idx;
            //         break;
            //     }
            // }

            if (r > time)
            {
                answer[idx] = 0;
                continue;
            }
            
            llong cntPositive = tree.query(r, time).sumPositive;
            llong cntNegative = tree.query(r, time).sumNegative;
            if (r > 1)
            {
                assert(tree.query(r - 1, time).minPrefix + (r == 2 ? 0 : tree.query(1, r - 2).maxSuffix) < 0);
                while (r > 1 && (tree.query(1, r - 1).maxSuffix > 0)) r--;
            }
            // assert(tree.query(r, time).minPrefix >= 0);

            if (val + cntNegative > cntPositive) answer[idx] = 0;
            else
            {
                int start = r;
                l = start - 1; r = time + 1;
                while (l < r - 1)
                {
                    mid = (l + r) / 2;
                    llong pos = tree.query(start, mid).sumPositive;
                    if (pos < cntNegative + val) l = mid;
                    else r = mid;
                }

                assert(r != time + 1);
                answer[idx] = tree.query(r, r).c;
                assert(answer[idx] != 0);
            }
        }
    }
}

void input()
{
    std::cin >> n >> m >> q;
    for (int i = 1 ; i <= q ; ++i)
    {
        int qType;
        std::cin >> qType;
        if (qType == 1)
        {
            int l, r, c, val;
            std::cin >> l >> r >> c >> val;
            activate[l].push_back({true, val, c, i});
            deactivate[r + 1].push_back({true, val, c, i});
            continue;
        }

        if (qType == 2)
        {
            int l, r, c, val;
            std::cin >> l >> r >> val;
            activate[l].push_back({false, val, 0, i});
            deactivate[r + 1].push_back({false, val, 0, i});
            continue;
        }

        assert(qType == 3);
        int pos;
        llong k;
        std::cin >> pos >> k;
        v[pos].push_back({i, k, ++cntServices});
    }
}

void print()
{
    for (int i = 1 ; i <= cntServices ; ++i)
    {
        std::cout << answer[i] << '\n';
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();
    print();

    return 0;
}

Compilation message

foodcourt.cpp: In function 'void input()':
foodcourt.cpp:236:23: warning: unused variable 'c' [-Wunused-variable]
  236 |             int l, r, c, val;
      |                       ^

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 65884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 65884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 68948 KB Output is correct
2 Correct 197 ms 69080 KB Output is correct
3 Incorrect 229 ms 68980 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1050 ms 76512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 65884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 68476 KB Output is correct
2 Correct 369 ms 68676 KB Output is correct
3 Correct 395 ms 68948 KB Output is correct
4 Correct 246 ms 67932 KB Output is correct
5 Correct 341 ms 68436 KB Output is correct
6 Correct 356 ms 68768 KB Output is correct
7 Correct 261 ms 67888 KB Output is correct
8 Correct 246 ms 67620 KB Output is correct
9 Correct 327 ms 68024 KB Output is correct
10 Correct 234 ms 67812 KB Output is correct
11 Correct 346 ms 68384 KB Output is correct
12 Correct 366 ms 68412 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 65884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 65884 KB Output isn't correct
2 Halted 0 ms 0 KB -