oj.uz

답안 #930786

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
930786 2024-02-20T12:17:05 Z boris_mihov 푸드 코트 (JOI21_foodcourt) C++17
13 / 100
 380 ms 158292 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;
            }

            if (r > time)
            {
                answer[idx] = 0;
                continue;
            }
            
            llong cntPositive = tree.query(r, time).sumPositive;
            llong cntNegative = tree.query(r, time).sumNegative;
            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:222:23: warning: unused variable 'c' [-Wunused-variable]
  222 |             int l, r, c, val;
      |                       ^

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 62 ms 133200 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 62 ms 133200 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 69900 KB Output is correct
2 Correct 197 ms 69844 KB Output is correct
3 Incorrect 222 ms 69712 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 297 ms 158292 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 62 ms 133200 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 327 ms 69584 KB Output is correct
2 Correct 357 ms 69748 KB Output is correct
3 Correct 380 ms 69816 KB Output is correct
4 Correct 247 ms 68896 KB Output is correct
5 Correct 313 ms 69384 KB Output is correct
6 Correct 376 ms 69896 KB Output is correct
7 Correct 267 ms 68612 KB Output is correct
8 Correct 264 ms 68544 KB Output is correct
9 Correct 341 ms 69048 KB Output is correct
10 Correct 246 ms 68688 KB Output is correct
11 Correct 349 ms 69456 KB Output is correct
12 Correct 367 ms 69484 KB Output is correct

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 62 ms 133200 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 62 ms 133200 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -