Submission #502431

#	Time	Username	Problem	Language	Result	Execution time	Memory
502431		cig32	Food Court (JOI21_foodcourt)	C++17	7 / 100	1102 ms	524292 KiB

foodcourt

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
    int u = uniform_int_distribution<int>(x, y)(rng);
    return u;
}
int bm(int b, int p) { // bigmod
    if(p==0) return 1;
    int r = bm(b, p/2);
    if(p&1) return (((r*r) % MOD) * b) % MOD;
    return (r*r) % MOD;
}
int N, M, Q;
deque<pair<int, int> > ok[MAXN];
void join(int l, int r, int c, int k) {
    for(int i=l; i<=r; i++) ok[i].push_back({c, k});
}
void leave(int l, int r, int k) {
    for(int i=l; i<=r; i++) {
        int m = k;
        while(ok[i].size() && m > 0) {
            pair<int, int> f = ok[i].front();
            if(m >= f.second) {
                m -= f.second;
                ok[i].pop_front();
            }
            else {
                f.second -= m;
                ok[i].pop_front();
                ok[i].push_front(f);
                break;
            }
        }
    }
}
int service(int a, int b) {
    stack<pair<int, int> > st;
    int ans = 0;
    while(ok[a].size()) {
        pair<int, int> f = ok[a].front();
        if(b <= f.second) {
            ans = f.first;
            break;
        }
        else b -= f.second;
        st.push(f);
        ok[a].pop_front();
    }
    while(st.size()) {
        ok[a].push_front(st.top());
        st.pop();
    }
    return ans;
}
void solve(int tc) {
    cin >> N >> M >> Q;
    while(Q--) {
        int t;
        cin >> t;
        if(t == 1) {
            int l, r, c, k;
            cin >> l >> r >> c >> k;
            join(l, r, c, k);
        }
        else if(t == 2) {
            int l, r, k;
            cin >> l >> r >> k;
            leave(l, r, k);
        }
        else {
            int a, b;
            cin >> a >> b;
            cout << service(a, b) << "\n";
        }
    }
}
int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1; //cin >> t;
    for(int i=1; i<=t; i++) {
        solve(i);
    }
}

• 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