Submission #954660

#	Time	Username	Problem	Language	Result	Execution time	Memory
954660		boris_mihov	Food Court (JOI21_foodcourt)	C++17	100 / 100	596 ms	93380 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;
        int minPrefixPos;
        llong sum;
        int c;
 
        Node()
        {
            maxSuffix = minPrefix = minPrefixPos = 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);
            if (minPrefix == left.minPrefix) minPrefixPos = left.minPrefixPos;
            else minPrefixPos = right.minPrefixPos;

            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);
            if (minPrefixPos == 0 || minPrefix == sum + right.minPrefix) minPrefixPos = right.minPrefixPos;
            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);
        }

        friend Node operator + (const Node &left, const Node &right)
        {
            Node result;
            result.sum = left.sum + right.sum;
            result.sumPositive = left.sumPositive + right.sumPositive;
            result.sumNegative = left.sumNegative + right.sumNegative;
            result.minPrefix = std::min(left.minPrefix, left.sum + right.minPrefix);
            if (result.minPrefix == left.minPrefix) result.minPrefixPos = left.minPrefixPos;
            else result.minPrefixPos = right.minPrefixPos;

            result.maxSuffix = std::max(right.maxSuffix, right.sum + left.maxSuffix);
            result.c = std::max(left.c, right.c);
            return result;
        }
    };
 
    Node tree[4*MAXN];
    void build(int l, int r, int node)
    {
        if (l == r)
        {
            tree[node].minPrefixPos = l;
            return;
        }

        int mid = l + r >> 1;
        build(l, mid, 2*node);
        build(mid + 1, r, 2*node + 1);
        tree[node].assign(tree[2*node], tree[2*node + 1]);
    }
    
    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 = res + query(mid + 1, r, 2*node + 1, queryL, queryR);
        return res;
    }
 
    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 build()
    {
        build(1, q, 1);
    }
 
    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 query(1, q, 1, l, r).maxSuffix;
    }
 
    llong queryMinPrefix(int l, int r)
    {
        return query(1, q, 1, l, r).minPrefix;
    }
 
    Node query(int l, int r)
    {
        return query(1, q, 1, l, r);
    }

    int queryMinPrefixPos(int l, int r)
    {
        return query(1, q, 1, l, r).minPrefixPos;
    }
 
    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()
{
    tree.build();
    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 r = tree.queryMinPrefixPos(1, time); 
            r += (tree.query(1, r).sum < 0);
            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()
{
    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, val;
            std::cin >> l >> r >> val;
            activate[l].push_back({false, val, 0, i});
            deactivate[r + 1].push_back({false, val, 0, i});
            continue;
        }
 
        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 (stderr)

foodcourt.cpp: In member function 'void SegmentTree::build(int, int, int)':
foodcourt.cpp:111:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'void SegmentTree::update(int, int, int, const int&, const int&, const int&, const bool&)':
foodcourt.cpp:139:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  139 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'SegmentTree::Node SegmentTree::query(int, int, int, const int&, const int&)':
foodcourt.cpp:153:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  153 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'llong SegmentTree::find(int, int, int, const int&, const int&, const llong&)':
foodcourt.cpp:176:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  176 |         int 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