oj.uz

답안 #1065597

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1065597 2024-08-19T09:45:34 Z phoenix 푸드 코트 (JOI21_foodcourt) C++17
0 / 100
 114 ms 40272 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = (1 << 18);
#define cerr if (false) cout
struct node {
    ll sum = 0;
    ll pre = 0;
};
node tr[2 * N];

node combine(node a, node b) {
    node res;
    res.sum = a.sum + b.sum;
    res.pre = min(a.pre, a.sum + b.pre);
    return res;
}

void update(int pos, ll val) {
    cerr << "upd: " << pos << ' ' << val << '\n';
    tr[pos += N] = {val, min(0ll, val)};
    for (pos >>= 1; pos; pos >>= 1) 
        tr[pos] = combine(tr[2 * pos], tr[2 * pos + 1]);
    cerr << "tree: " << tr[1].sum << ' ' << tr[1].pre << '\n';
}
node get(int ql, int qr, int l = 0, int r = N - 1, int v = 1) {
    if (r < ql || l > qr)
        return node();
    if (ql <= l && r <= qr) 
        return tr[v];
    int m = (l + r) / 2;
    return combine(get(ql, qr, l, m, 2 * v), get(ql, qr, m + 1, r, 2 * v + 1)); 
}

ll cnt[2 * N];
void add(int v, ll a) {
    for (cnt[v += N] += a; v > 1; v >>= 1)
        cnt[v >> 1] = cnt[v] + cnt[v^1];
}
ll count(int ql, int qr, int l = 0, int r = N - 1, int v = 1) {
    if (r < ql || l > qr)   
        return 0;
    if (ql <= l && r <= qr)
        return cnt[v];
    int m = (l + r) / 2;
    return count(ql, qr, l, m, 2 * v) + count(ql, qr, m + 1, r, 2 * v + 1);
}

int n, m, q;

vector<pair<int, int>> join[N][2];
vector<pair<int, int>> leave[N][2];
vector<pair<int, int>> service[N];  

map<int, int> timeToGroup;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int t = 1; t <= q; t++) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r, k, c;
            cin >> l >> r >> c >> k;
            timeToGroup[t] = c;
            join[l][0].push_back({t, k});
            join[r][1].push_back({t, k});
        }
        if (type == 2) {
            int l, r, k;
            cin >> l >> r >> k;
            leave[l][0].push_back({t, k});
            leave[r][1].push_back({t, k});
        }
        if (type == 3) {
            int a, b;
            cin >> a >> b;
            service[a].push_back({t, b});
        }
    }
    
    vector<int> res(q + 1, -2);

    for (int i = 1; i <= n; i++) {
        for (auto o : join[i][0]) {
            int t = o.first, k = o.second;
            update(t, +k);
            add(t, +k);
        }
        for (auto o : leave[i][0]) {
            int t = o.first, k = o.second;
            update(t, -k);
        }
        for (auto [t, b] : service[i]) {
            int num = get(1, t).sum - get(1, t).pre;
            // cerr << "service: " << t << ' ' << b << '\n';
            // cerr << get(1, t).sum << '\n';
            if (num < b) {
                res[t] = 0;
                continue;
            }
            int l = 0, r = t + 1;
            while (r - l > 1) {
                int m = (l + r) / 2;
                if (count(m, t) >= b)
                    l = m;
                else 
                    r = m;
            }
            res[t] = timeToGroup[l];
        }
        for (auto o : join[i][1]) {
            int t = o.first, k = o.second;
            update(t, 0);
            add(t, -k);
        }
        for (auto o : leave[i][1]) {
            int t = o.first, k = o.second;
            update(t, 0);
        }
    }
    for (int i = 1; i <= q; i++) {
        if (res[i] != -2)
            cout << res[i] << '\n';
    }
}

Compilation message

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:122:30: warning: unused variable 'k' [-Wunused-variable]
  122 |             int t = o.first, k = o.second;
      |                              ^

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 39508 KB Output is correct
2 Correct 71 ms 40272 KB Output is correct
3 Correct 66 ms 39508 KB Output is correct
4 Incorrect 62 ms 39504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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