oj.uz

답안 #954656

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954656 2024-03-28T09:46:26 Z boris_mihov 푸드 코트 (JOI21_foodcourt) C++17
13 / 100
 545 ms 84516 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;
        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);
        }
    };
 
    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 += 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

foodcourt.cpp: In member function 'void SegmentTree::build(int, int, int)':
foodcourt.cpp:96:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |         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:124:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  124 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'SegmentTree::Node SegmentTree::query(int, int, int, const int&, const int&)':
foodcourt.cpp:138:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  138 |         int mid = l + r >> 1;
      |                   ~~^~~
foodcourt.cpp: In member function 'llong SegmentTree::find(int, int, int, const int&, const int&, const llong&)':
foodcourt.cpp:161:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  161 |         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
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 76372 KB Output is correct
2 Correct 119 ms 76576 KB Output is correct
3 Correct 128 ms 76640 KB Output is correct
4 Correct 97 ms 75752 KB Output is correct
5 Correct 94 ms 76164 KB Output is correct
6 Correct 137 ms 76604 KB Output is correct
7 Correct 80 ms 75712 KB Output is correct
8 Correct 67 ms 75464 KB Output is correct
9 Correct 89 ms 75976 KB Output is correct
10 Correct 73 ms 75608 KB Output is correct
11 Correct 99 ms 76368 KB Output is correct
12 Correct 113 ms 76380 KB Output is correct

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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