oj.uz

답안 #480764

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
480764 2021-10-18T03:22:26 Z fishy15 푸드 코트 (JOI21_foodcourt) C++17
13 / 100
 485 ms 53176 KB 
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>

#define ll long long
#define ld long double
#define eps 1e-8
#define MOD 1000000007

#define int long long

#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f

// change if necessary
#define MAXN 250010

using namespace std;

template<typename T>
T &ckmin(T &a, T b) {
    return a = min(a, b);
}

struct BIT {
    int n;
    vector<ll> bit;

    BIT(int n) : n(n), bit(n) {}

    void upd(int x, ll q) {
        x++;
        while (x <= n) {
            bit[x - 1] += q;
            x += x & -x;
        }
    }

    ll qry(int x) {
        ll res = 0;
        while (x > 0) {
            res += bit[x - 1];
            x -= x & -x;
        }
        return res;
    }

    int bsearch(ll r) {
        int cur = 0;
        ll sum = 0;
        for (int i = (1 << 20); i > 0; i /= 2) {
            if (cur + i <= n && sum + bit[cur + i - 1] <= r) {
                cur += i;
                sum += bit[cur - 1];
            }
        }
        return cur;
    }
};

BIT tot_add(0);

struct segtree {
    int n;
    vector<ll> st;
    vector<ll> lazy;

    segtree(int n) : n(n), st(4 * n), lazy(4 * n) {}

    void push(int v, int l, int r) {
        if (l + 1 != r) {
            lazy[2 * v] += lazy[v];
            lazy[2 * v + 1] += lazy[v];
            ckmin(lazy[2 * v], st[2 * v]);
            ckmin(lazy[2 * v + 1], st[2 * v + 1]);
        }

        st[v] -= lazy[v];
        lazy[v] = 0;
    }

    void upd(int x, int y, ll q) { upd(1, 0, n, x, y, q); }
    void upd(int v, int l, int r, int x, int y, ll q) {
        push(v, l, r);
        ckmin(q, st[v]);
        if (r <= x || l >= y) return;
        if (x <= l && r <= y) {
            lazy[v] += q;
            push(v, l, r);
        } else {
            int m = (l + r) / 2;
            upd(2 * v, l, m, x, y, q);
            upd(2 * v + 1, m, r, x, y, q);
            st[v] = max(st[2 * v], st[2 * v + 1]);
        }
    }

    ll qry(int a, ll b) { return qry(1, 0, n, a, b); }
    ll qry(int v, int l, int r, int a, ll b) {
        push(v, l, r);
        if (l + 1 == r) {
            if (b >= st[v]) {
                return -1;
            } else {
                return tot_add.qry(a + 1) - st[v] + b;
            }
        } else {
            int m = (l + r) / 2;
            if (a < m) {
                return qry(2 * v, l, m, a, b);
            } else {
                return qry(2 * v + 1, m, r, a, b);
            }
        }
    }
};

int n, m, q;
array<ll, 5> qry[MAXN];
vector<pair<ll, int>> in_q;
vector<int> add[MAXN]; // elements to add to the queue
vector<int> rem[MAXN]; // elements to remove from the queue
vector<pair<ll, int>> to_ans[MAXN];
vector<ll> ans;

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m >> q;
    for (int i = 0; i < q; i++) {
        qry[i] = {0, 0, 0, 0, 0};
        cin >> qry[i][0];
        switch (qry[i][0]) {
            case 1: 
                cin >> qry[i][1] >> qry[i][2] >> qry[i][3] >> qry[i][4];
                break;
            case 2:
                cin >> qry[i][1] >> qry[i][2] >> qry[i][3];
                break;
            case 3:
                cin >> qry[i][1] >> qry[i][2];
                break;
        }
    }

    segtree st(n);
    tot_add = BIT(n);

    for (int i = 0; i < q; i++) {
        auto qq = qry[i];
        if (qq[0] == 1) {
            auto [t, l, r, c, k] = qq;
            l--;
            add[l].push_back(in_q.size());
            rem[r].push_back(in_q.size());
            in_q.push_back({k, c});
            st.upd(l, r, -k);
            tot_add.upd(l, k);
            tot_add.upd(r, -k);
        } else if (qq[0] == 2) {
            auto [t, l, r, k, _] = qq;
            l--;
            st.upd(l, r, k);
        } else {
            auto [t, a, b, _, __] = qq;
            a--; b--;
            int p_idx = st.qry(a, b);
            to_ans[a].push_back({p_idx, ans.size()});
            ans.emplace_back();
        }
    }

    int sz = in_q.size();
    BIT bit(sz);
    for (int i = 0; i < n; i++) {
        for (int x : add[i]) {
            bit.upd(x, in_q[x].first);
        }

        for (int x : rem[i]) {
            bit.upd(x, -in_q[x].first);
        }

        for (auto [loc, idx] : to_ans[i]) {
            if (loc == -1) {
                ans[idx] = 0;
            } else {
                int pos = bit.bsearch(loc);
                ans[idx] = in_q[pos].second;
            }
        }
    }

    for (int x : ans) {
        cout << x << '\n';
    }

    return 0;
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 29264 KB Output is correct
2 Correct 111 ms 29420 KB Output is correct
3 Correct 108 ms 30304 KB Output is correct
4 Correct 85 ms 27704 KB Output is correct
5 Correct 106 ms 29048 KB Output is correct
6 Correct 118 ms 30280 KB Output is correct
7 Correct 42 ms 23336 KB Output is correct
8 Correct 39 ms 23068 KB Output is correct
9 Correct 61 ms 29112 KB Output is correct
10 Correct 79 ms 26776 KB Output is correct
11 Correct 101 ms 29376 KB Output is correct
12 Correct 103 ms 29544 KB Output is correct

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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