제출 #1313193

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313193		hihihahahoho	푸드 코트 (JOI21_foodcourt)	C++20	100 / 100	517 ms	32232 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;

#define file(name) if (fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
#define int long long
#define fi first
#define se second

const int mxN = 3e5 + 5;

struct Query {
    int type, a, b, c, d;
};

int n, m, q;
int bit[2][mxN], st[2][4 * mxN], ans[mxN], L[mxN], R[mxN];
Query qr[mxN];

void bit_upd(int x, int i, int v) {
    for (; i <= n; i += i & -i) bit[x][i] += v;
}

void bit_upd_range(int x, int l, int r, int v) {
    bit_upd(x, l, v);
    bit_upd(x, r + 1, -v);
}

int bit_get(int x, int i) {
    int res = 0;
    for (; i > 0; i -= i & -i) res += bit[x][i];
    return res;
}

void bit_clear(int x) {
    for (int i = 1; i <= n; i++) bit[x][i] = 0;
}

void add(int id, int x, int y) {
    st[0][id] += x;
    st[1][id] = max(st[1][id] + x, y);
}

void down(int id) {
    add(id << 1, st[0][id], st[1][id]);
    add(id << 1 | 1, st[0][id], st[1][id]);
    st[0][id] = st[1][id] = 0;
}

void seg_upd(int id, int l, int r, int u, int v, int w) {
    if (l > v || r < u) return;
    if (u <= l && r <= v) {
        add(id, w, 0);
        return;
    }
    down(id);
    int m = (l + r) >> 1;
    seg_upd(id << 1, l, m, u, v, w);
    seg_upd(id << 1 | 1, m + 1, r, u, v, w);
}

int seg_get(int id, int l, int r, int u) {
    if (l == r) return max(st[0][id], st[1][id]);
    down(id);
    int m = (l + r) >> 1;
    if (u <= m) return seg_get(id << 1, l, m, u);
    return seg_get(id << 1 | 1, m + 1, r, u);
}

signed main() {
    file("test");
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> q;

    for (int i = 0; i < q; i++) {
        int type; cin >> type;
        qr[i].type = type;

        if (type == 1) {
            cin >> qr[i].a >> qr[i].b >> qr[i].c >> qr[i].d;
            bit_upd_range(0, qr[i].a, qr[i].b, qr[i].d);
            seg_upd(1, 1, n, qr[i].a, qr[i].b, qr[i].d);
        }

        if (type == 2) {
            cin >> qr[i].a >> qr[i].b >> qr[i].c;
            seg_upd(1, 1, n, qr[i].a, qr[i].b, -qr[i].c);
        }

        if (type == 3) {
            cin >> qr[i].a >> qr[i].b;
            ans[i] = -1;
            L[i] = 0;
            R[i] = i - 1;
            qr[i].b += bit_get(0, qr[i].a) - seg_get(1, 1, n, qr[i].a);
        }
    }

    while (true) {
        vector<pair<int,int>> check;

        for (int i = 0; i < q; i++) if (qr[i].type == 3 && L[i] <= R[i]) {
            check.push_back({ (L[i] + R[i]) >> 1, i });
        }

        if (check.empty()) break;

        sort(check.begin(), check.end());
        bit_clear(1);

        int j = 0;
        for (int t = 0; t < (int)check.size(); t++) {
            int curMid = check[t].fi;
            int curID  = check[t].se;

            while (j <= curMid) {
                if (qr[j].type == 1) bit_upd_range(1, qr[j].a, qr[j].b, qr[j].d);
                j++;
            }

            if (bit_get(1, qr[curID].a) >= qr[curID].b) ans[curID] = curMid, R[curID] = curMid - 1;
            else L[curID] = curMid + 1;
        }
    }

    for (int i = 0; i < q; i++) if (qr[i].type == 3) {
        cout << (ans[i] == -1 ? 0 : qr[ans[i]].c) << '\n';
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:4:56: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define file(name) if (fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
      |                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:70:5: note: in expansion of macro 'file'
   70 |     file("test");
      |     ^~~~
foodcourt.cpp:4:88: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define file(name) if (fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
      |                                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:70:5: note: in expansion of macro 'file'
   70 |     file("test");
      |     ^~~~

• 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