Submission #930813

#	Time	Username	Problem	Language	Result	Execution time	Memory
930813		boris_mihov	Food Court (JOI21_foodcourt)	C++17	100 / 100	935 ms	85828 KiB

foodcourt

#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::min(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 (stderr)

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: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11