제출 #797301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
797301		vjudge1	푸드 코트 (JOI21_foodcourt)	C++17	7 / 100	448 ms	524288 KiB

foodcourt

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 70000;
const int B = 266;

int n, m, q;

deque<pair<int, ll>> g[N]; 
struct obj {
    ll pos, c, k;
};

deque<obj> que[N + 10], bl_q[N / B + 10];

void add(deque<obj> &q, int c, ll k) {
    if(q.empty()) q.push_back({0, c, k});
    else q.push_back({(q.back().pos + q.back().k), c, k});
}

ll find(deque<obj> &q, ll b) {
    if(q.empty() || q.back().pos + q.back().k <= b || b < 0) return 0;
    int l = 0, r = (int)q.size();
    while(r - l > 1) {
        int mid = (l + r) / 2;
        if(b < q[mid].pos) r = mid;
        else l = mid;
    }
    return q[l].c;
}
void push(int bl) {
    if(bl_q[bl].empty()) return;
    for(int i = bl * B; i < (bl + 1) * B; i++) {
        for(obj z : bl_q[bl]) 
            add(que[i], z.c, z.k);
    }
    bl_q[bl].clear();
}

ll answer(int a, ll b) {
    b--;
    ll ans = find(que[a], b);
    if(ans) return ans;
    if(!que[a].empty()) b -= que[a].back().pos + que[a].back().k;
    return find(bl_q[a / B], b);
}

vector<vector<ll>> qr;
void solve() {
    for(auto g : qr) {
        if(g[0] == 1) {
            ll l, r, c, k;
            l = g[1], r = g[2], c = g[3], k = g[4];
            while(l <= r) {
                bool flag = (l % B == 0 && l + B - 1 <= r);
                if(flag) add(bl_q[l / B], c, k), l += B;
                else {
                    push(l / B);
                    add(que[l], c, k);
                    l++;
                }
            }
        }
        if(g[0] == 3) {
            ll a, b;
            a = g[1], b = g[2];
            cout << answer(a, b) << '\n';
        }
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;
    if(n <= 2000 && q <= 2000) {
        for(int i = 0; i < q; i++) {
            int t;
            cin >> t;
            if(t == 1) {
                ll l, r, c, k;
                cin >> l >> r >> c >> k;
                for(int j = l; j <= r; j++) {
                    g[j].push_back({c, k});
                }
            }
            if(t == 2) {
                ll l, r, k;
                cin >> l >> r >> k;
                for(int j = l; j <= r; j++) {
                    int p = k;
                    while(!g[j].empty() && g[j].front().second <= p) {
                        p -= g[j].front().second;
                        g[j].pop_front();
                    }
                    if(!g[j].empty()) 
                        g[j][0].second -= p;
                }
            }
            if(t == 3) {
                ll a, b;
                cin >> a >> b;
                int ans = 0;
                for(auto [c, k] : g[a]) {
                    if(b > k) b -= k;
                    else {ans = c; break;}
                }
                cout << ans << '\n';    
                  
            }
        }
        return 0;
    }
    bool flag = 1;
    for(int i = 0; i < q; i++) {
        int t;
        cin >> t;
        ll l, r, c, k, a, b;
        if(t == 1) {
            cin >> l >> r >> c >> k;
            qr.push_back({t, l, r, c, k});
        }
        if(t == 2) {
            cin >> l >> r >> k;
            flag = 0;
            qr.push_back({t, l, r, k});
        }
        if(t == 3) {
            cin >> a >> b;
            qr.push_back({t, a, b});
        }
    } 
    if(flag) {
        solve();
    }
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 21
• Subtask 5: 0 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11