oj.uz

Submission #930796

# Submission time Handle Problem Language Result Execution time Memory
930796 2024-02-20T12:30:01 Z boris_mihov Food Court (JOI21_foodcourt) C++17
13 / 100
 1000 ms 76748 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).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 242 ms 68988 KB Output is correct
2 Correct 252 ms 68944 KB Output is correct
3 Incorrect 227 ms 68988 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 1034 ms 76748 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 311 ms 68476 KB Output is correct
2 Correct 373 ms 68728 KB Output is correct
3 Correct 357 ms 68796 KB Output is correct
4 Correct 261 ms 67916 KB Output is correct
5 Correct 307 ms 68360 KB Output is correct
6 Correct 364 ms 68748 KB Output is correct
7 Correct 265 ms 68092 KB Output is correct
8 Correct 245 ms 67536 KB Output is correct
9 Correct 340 ms 68144 KB Output is correct
10 Correct 273 ms 67924 KB Output is correct
11 Correct 359 ms 68476 KB Output is correct
12 Correct 370 ms 68432 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 -