Submission #797257

#	Time	Username	Problem	Language	Result	Execution time	Memory
797257		vjudge1	Food Court (JOI21_foodcourt)	C++17	0 / 100	410 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], bl_q[N / B];

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 = -1, 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) {
    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 {
                    if(!bl_q[l / B].empty()) 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: 0 / 2
• Subtask 2: 0 / 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