oj.uz

답안 #930812

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
930812 2024-02-20T12:58:55 Z boris_mihov 푸드 코트 (JOI21_foodcourt) C++17
13 / 100
 713 ms 76788 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

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

const int BUFF_SIZE = 1e5;
char buff[BUFF_SIZE];
int buffPos = BUFF_SIZE-1;

void readChar() 
{
    if (++buffPos == BUFF_SIZE) fread(buff, BUFF_SIZE, 1, stdin), buffPos = 0;
}

void readInt(int &num) 
{
    num = 0;
    for (; '0' > buff[buffPos] || buff[buffPos] > '9' ; readChar());
    for (; '0' <= buff[buffPos] && buff[buffPos] <= '9' ; readChar())
    {
        num = 10*num + buff[buffPos]-'0';
    }
}

void readLong(llong &num) 
{
    num = 0;
    for (; '0' > buff[buffPos] || buff[buffPos] > '9' ; readChar());
    for (; '0' <= buff[buffPos] && buff[buffPos] <= '9' ; readChar())
    {
        num = 10*num + buff[buffPos]-'0';
    }
}

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;
        }   

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

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

    Node tree[4*MAXN];
    void update(int l, int r, int node, const int &queryPos, const int &queryVal, const int &queryC, const 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 = std::min(0LL, tree[node].sum);
            tree[node].maxSuffix = std::max(0LL, tree[node].sum);
            return;
        }

        int mid = l + r >> 1;
        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].assign(tree[2*node], tree[2*node + 1]);
    }

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

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

    std::pair <llong,llong> queryMaxSuffix(int l, int r, int node, const int &queryL, const int &queryR)
    {
        if (queryL <= l && r <= queryR)
        {
            return {tree[node].maxSuffix, tree[node].sum};
        }

        int mid = l + r >> 1;
        llong left = 0, sL = 0, right = 0, sR = 0;
        if (queryL <= mid) 
        {
            auto p = queryMaxSuffix(l, mid, 2*node, queryL, queryR);
            left = p.first; sL = p.second;
        }

        if (mid + 1 <= queryR) 
        {
            auto p = queryMaxSuffix(mid + 1, r, 2*node + 1, queryL, queryR);
            right = p.first; sR = p.second;
        }

        return {std::max(right, sR + left), sL + sR};
    }

    std::pair <llong,llong> queryMinPrefix(int l, int r, int node, const int &queryL, const int &queryR)
    {
        if (queryL <= l && r <= queryR)
        {
            return {tree[node].minPrefix, tree[node].sum};
        }

        int mid = l + r >> 1;
        llong left = 0, sL = 0, right = 0, sR = 0;
        if (queryL <= mid) 
        {
            auto p = queryMinPrefix(l, mid, 2*node, queryL, queryR);
            left = p.first; sL = p.second;
        }

        if (mid + 1 <= queryR) 
        {
            auto p = queryMinPrefix(mid + 1, r, 2*node + 1, queryL, queryR);
            right = p.first; sR = p.second;
        }

        return {std::max(left, sL + right), sL + sR};
    }

    llong find(int l, int r, int node, const int &queryL, const int &queryR, const llong &k)
    {
        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 >> 1;
        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);
    }

    llong queryMaxSuffix(int l, int r)
    {
        return queryMaxSuffix(1, q, 1, l, r).first;
    }

    llong queryMinPrefix(int l, int r)
    {
        return queryMinPrefix(1, q, 1, l, r).first;
    }

    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 >> 1;
                llong res = tree.queryMinPrefix(mid, time);
                if (mid > 1) res += tree.queryMaxSuffix(1, mid - 1);
                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;

            if (val + cntNegative > cntPositive) answer[idx] = 0;
            else answer[idx] = tree.find(r, time, val + cntNegative);
        }
    }
}

void input()
{
    readInt(n);
    readInt(m);
    readInt(q);
    for (int i = 1 ; i <= q ; ++i)
    {
        int qType;
        readInt(qType);
        if (qType == 1)
        {
            int l, r, c, val;
            readInt(l);
            readInt(r);
            readInt(c);
            readInt(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, val;
            readInt(l);
            readInt(r);
            readInt(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;
        readInt(pos);
        readLong(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 member function 'void SegmentTree::update(int, int, int, const int&, const int&, const int&, const bool&)':
foodcourt.cpp:105:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'SegmentTree::Node SegmentTree::query(int, int, int, const int&, const int&)':
foodcourt.cpp:119:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'std::pair<long long int, long long int> SegmentTree::queryMaxSuffix(int, int, int, const int&, const int&)':
foodcourt.cpp:132:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  132 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'std::pair<long long int, long long int> SegmentTree::queryMinPrefix(int, int, int, const int&, const int&)':
foodcourt.cpp:156:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  156 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'llong SegmentTree::find(int, int, int, const int&, const int&, const llong&)':
foodcourt.cpp:190:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  190 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In function 'void solve()':
foodcourt.cpp:265:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  265 |                 mid = l + r >> 1;
      |                       ~~^~~
foodcourt.cpp: In function 'void readChar()':
foodcourt.cpp:20:38: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     if (++buffPos == BUFF_SIZE) fread(buff, BUFF_SIZE, 1, stdin), buffPos = 0;
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 65880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 65880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 144 ms 69088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 713 ms 76788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 65880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 68580 KB Output is correct
2 Correct 189 ms 68836 KB Output is correct
3 Correct 172 ms 68900 KB Output is correct
4 Correct 117 ms 68028 KB Output is correct
5 Correct 170 ms 68472 KB Output is correct
6 Correct 179 ms 68948 KB Output is correct
7 Correct 100 ms 68012 KB Output is correct
8 Correct 108 ms 67728 KB Output is correct
9 Correct 144 ms 68296 KB Output is correct
10 Correct 113 ms 67932 KB Output is correct
11 Correct 170 ms 68496 KB Output is correct
12 Correct 159 ms 68688 KB Output is correct

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 65880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 65880 KB Output isn't correct
2 Halted 0 ms 0 KB -