oj.uz

답안 #852620

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
852620 2023-09-22T08:29:48 Z danikoynov 푸드 코트 (JOI21_foodcourt) C++14
13 / 100
 502 ms 97144 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 <= 4 * 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 9 ms 43868 KB Output is correct
2 Correct 9 ms 43868 KB Output is correct
3 Correct 8 ms 43888 KB Output is correct
4 Correct 8 ms 43864 KB Output is correct
5 Runtime error 40 ms 88632 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 49008 KB Output is correct
2 Correct 116 ms 49428 KB Output is correct
3 Correct 114 ms 49172 KB Output is correct
4 Correct 109 ms 48980 KB Output is correct
5 Correct 132 ms 49404 KB Output is correct
6 Correct 118 ms 49492 KB Output is correct
7 Runtime error 55 ms 93784 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 491 ms 55380 KB Output is correct
2 Correct 502 ms 54448 KB Output is correct
3 Correct 460 ms 55888 KB Output is correct
4 Correct 303 ms 55124 KB Output is correct
5 Correct 254 ms 54184 KB Output is correct
6 Correct 398 ms 56444 KB Output is correct
7 Runtime error 97 ms 97144 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

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

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 47956 KB Output is correct
2 Correct 60 ms 47952 KB Output is correct
3 Correct 61 ms 48076 KB Output is correct
4 Correct 47 ms 47700 KB Output is correct
5 Correct 57 ms 47816 KB Output is correct
6 Correct 64 ms 47956 KB Output is correct
7 Correct 24 ms 44760 KB Output is correct
8 Correct 24 ms 44960 KB Output is correct
9 Correct 44 ms 47136 KB Output is correct
10 Correct 41 ms 46928 KB Output is correct
11 Correct 55 ms 47188 KB Output is correct
12 Correct 56 ms 47184 KB Output is correct

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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