oj.uz

답안 #852619

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
852619 2023-09-22T08:29:31 Z danikoynov 푸드 코트 (JOI21_foodcourt) C++14
13 / 100
 552 ms 97216 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 250010;
const ll inf = 1e18;
struct node
{
    ll min_val, min_lf, min_rf;

    node(ll  _min_val = inf, ll _min_lf = -1, ll _min_rf = -1)
    {
        min_val = _min_val;
        min_lf = _min_lf;
        min_rf = _min_rf;
    }
};

node merge_nodes(node lf, node rf)
{
    if (lf.min_val < rf.min_val)
        return lf;
    if (rf.min_val < lf.min_val)
    return rf;

    node cur = lf;
    if (lf.min_rf == rf.min_lf - 1)
    {
        cur.min_rf = rf.min_rf;
    }
    return cur;
}

struct segment_tree
{
    node tree[4 * maxn];
    ll lazy[4 * maxn];

    void push_lazy(int root, int left, int right)
    {
        tree[root].min_val += lazy[root];
        if (left != right)
        {
            lazy[root * 2] += lazy[root];
            lazy[root * 2 + 1] += lazy[root];
        }
        lazy[root] = 0;
    }

    void build(int root, int left, int right)
    {
        if (left == right)
        {
            tree[root].min_lf = left;
            tree[root].min_rf = right;
            tree[root].min_val = 0;
            return;
        }

        int mid = (left + right) / 2;
        build(root * 2, left, mid);
        build(root * 2 + 1, mid + 1, right);

        tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
    }
    void update(int root, int left, int right, int qleft, int qright, ll cur)
    {
        push_lazy(root, left, right);

        if (left > qright || right < qleft)
            return;

        if (left >= qleft && right <= qright)
        {
            lazy[root] = cur;
            push_lazy(root, left, right);
            return;
        }

        int mid = (left + right) / 2;
        update(root * 2, left, mid, qleft, qright, cur);
        update(root * 2 + 1, mid + 1, right, qleft, qright, cur);

        tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
    }

    node query(int root, int left, int right, int qleft, int qright)
    {
        push_lazy(root, left, right);
        if (left > qright || right < qleft)
            return node();
        if (left >= qleft && right <= qright)
            return tree[root];

        int mid = (left + right) / 2;
        return merge_nodes(query(root * 2, left, mid, qleft, qright),
                           query(root * 2 + 1, mid + 1, right, qleft, qright));
    }

};



int n, m, q;
void input()
{
    cin >> n >> m >> q;
}

struct task
{
    int idx;
    ll  pos;

    task(int _idx = 0, ll _pos = 0)
    {
        idx = _idx;

        pos = _pos;
    }
};

struct bit
{
    ll fen[maxn];

    void update(int pos, ll val)
    {
        for (int i = pos; i < maxn; i += (i & -i))
            fen[i] += val;
    }

    ll query(int pos)
    {
        ll sum = 0;
        for (int i = pos; i > 0; i -= (i & -i))
            sum += fen[i];
        return sum;
    }

    void range_update(int l, int r, ll v)
    {
        update(l, v);
        update(r + 1, - v);
    }

    int find_kth(ll to)
    {
        int pos = 0;
        ll sum = 0;
        for (int bit = 20; bit >= 0; bit --)
        {
            if (pos + (1 << bit) > maxn)
                continue;
            ll new_sum = sum + fen[pos + (1 << bit)];
            if (new_sum < to)
            {
                pos = pos + (1 << bit);
                sum = new_sum;
            }
        }
        return pos + 1;
    }
};

vector < task > ask[maxn];
segment_tree line_tree;
bit pass_tree;
int ans[maxn];


pair < int, ll > add[maxn];
vector < int > upd[maxn];
int query_cnt = 0;

void simulate()
{
    line_tree.build(1, 1, n);
    int t, l, r, c, a; /// careful overflow
    ll k, b;

    int cnt = 0;
    for (int i = 1; i <= q; i ++)
    {
        cin >> t;
        if (t == 1)
        {
            cin >> l >> r >> c >> k;
            line_tree.update(1, 1, n, l, r, k);
            add[i] = {c, k};
            upd[l].push_back(i);
            upd[r + 1].push_back(-i);
        }
        else
        if (t == 2)
        {
            cin >> l >> r >> k;
            line_tree.update(1, 1, n, l, r, -k);
            pass_tree.range_update(l, r, k);
            node cur;
            while(true)
            {
                cur = line_tree.query(1, 1, n, l, r);
                if (cur.min_val >= 0)
                    break;
                pass_tree.range_update(cur.min_lf, cur.min_rf, cur.min_val);
                line_tree.update(1, 1, n, cur.min_lf, cur.min_rf, - cur.min_val);
                cnt ++;
            }
        }
        else
        {
            cin >> a >> b;
            query_cnt ++;
            if (line_tree.query(1, 1, n, a, a).min_val < b)
            {
                ans[query_cnt] = 0;
            }
            else
            {
                ///cout << "here " << query_cnt << " " << pass_tree.query(a) << " " << line_tree.query(1, 1, n, a, a).min_val << endl;
                ask[a].push_back(task(query_cnt, pass_tree.query(a) + b));
            }
        }
    }
    assert(cnt <= 2 * n);
}

bit active;
void answer_tasks()
{
    for (int i = 1; i <= n; i ++)
    {
        for (int cur : upd[i])
        {
            if (cur > 0)
            {
                active.update(cur, add[cur].second);
            }
            else
            {
                active.update(-cur, - add[-cur].second);
            }
        }

        for (task cur : ask[i])
        {
            ans[cur.idx] = add[active.find_kth(cur.pos)].first;
            ///cout << cur.idx << " : " << cur.shop << " " << cur.pos << endl;
        }
    }
    for (int i = 1; i <= query_cnt; i ++)
    {
        cout << ans[i] << endl;
    }
}

void solve()
{
    input();
    simulate();
    answer_tasks();
}

int main()
{
    speed();
    solve();
    return 0;
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 43864 KB Output is correct
2 Correct 8 ms 43864 KB Output is correct
3 Correct 8 ms 44120 KB Output is correct
4 Correct 9 ms 43864 KB Output is correct
5 Runtime error 38 ms 88660 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 43864 KB Output is correct
2 Correct 8 ms 43864 KB Output is correct
3 Correct 8 ms 44120 KB Output is correct
4 Correct 9 ms 43864 KB Output is correct
5 Runtime error 38 ms 88660 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 48992 KB Output is correct
2 Correct 139 ms 49488 KB Output is correct
3 Correct 109 ms 49168 KB Output is correct
4 Correct 147 ms 49292 KB Output is correct
5 Correct 119 ms 49516 KB Output is correct
6 Correct 116 ms 49488 KB Output is correct
7 Runtime error 54 ms 93624 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 494 ms 55376 KB Output is correct
2 Correct 552 ms 54300 KB Output is correct
3 Correct 437 ms 55760 KB Output is correct
4 Correct 304 ms 55120 KB Output is correct
5 Correct 262 ms 54276 KB Output is correct
6 Correct 358 ms 56344 KB Output is correct
7 Runtime error 97 ms 97216 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 43864 KB Output is correct
2 Correct 8 ms 43864 KB Output is correct
3 Correct 8 ms 44120 KB Output is correct
4 Correct 9 ms 43864 KB Output is correct
5 Runtime error 38 ms 88660 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 47952 KB Output is correct
2 Correct 61 ms 47956 KB Output is correct
3 Correct 62 ms 48208 KB Output is correct
4 Correct 46 ms 47684 KB Output is correct
5 Correct 54 ms 47952 KB Output is correct
6 Correct 71 ms 48208 KB Output is correct
7 Correct 23 ms 44756 KB Output is correct
8 Correct 23 ms 44856 KB Output is correct
9 Correct 48 ms 47136 KB Output is correct
10 Correct 42 ms 46928 KB Output is correct
11 Correct 61 ms 47172 KB Output is correct
12 Correct 59 ms 47184 KB Output is correct

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 43864 KB Output is correct
2 Correct 8 ms 43864 KB Output is correct
3 Correct 8 ms 44120 KB Output is correct
4 Correct 9 ms 43864 KB Output is correct
5 Runtime error 38 ms 88660 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 43864 KB Output is correct
2 Correct 8 ms 43864 KB Output is correct
3 Correct 8 ms 44120 KB Output is correct
4 Correct 9 ms 43864 KB Output is correct
5 Runtime error 38 ms 88660 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -