Submission #674625

#	Time	Username	Problem	Language	Result	Execution time	Memory
674625		someone	Food Court (JOI21_foodcourt)	C++14	100 / 100	409 ms	50788 KiB

foodcourt

#include <bits/stdc++.h>
#define int long long
#define mid ((deb + fin) >> 1)
using namespace std;

struct Node {
    int nbCl, infLen, addLen;
};

struct Req {
    bool isUpd;
    int id, add, req;
};

const int M = 1 << 18, N = 2 * M, INF = 1e18 + 42, MOD = 1e9 + 7;

Node node[N];
vector<Req> req[M];
int n, m, q, id[M], ans[M];

void addFin(int i, int add) {
    i += M;
    int j = i;
    while(i) {
        node[i].nbCl += add;
        i >>= 1;
    }
    i = j;
    node[i].addLen += add;
    while(i >>= 1) {
        node[i].addLen = node[i*2].addLen + node[i*2+1].addLen;
        node[i].infLen = max(node[i*2].infLen + node[i*2+1].addLen, node[i*2+1].infLen);
    }
}

void dimLen(int i, int add) {
    i += M;
    node[i].addLen += add;
    while(i >>= 1) {
        node[i].addLen = node[i*2].addLen + node[i*2+1].addLen;
        node[i].infLen = max(node[i*2].infLen + node[i*2+1].addLen, node[i*2+1].infLen);
    }
}

int getVal(int i) {
    i += M;
    int sum = node[i].nbCl;
    while(i) {
        if(i & 1)
            sum += node[i-1].nbCl;
        i >>= 1;
    }
    return sum;
}

int getLen(int i) {
    i += M;
    int infLen = node[i].infLen,
        addLen = node[i].addLen;
    while(i) {
        if(i & 1) {
            infLen = max(node[i-1].infLen + addLen, infLen);
            addLen += node[i-1].addLen;
        }
        i >>= 1;
    }
    return max(addLen, infLen);
}

int getId(int i, int deb, int fin, int val) {
    if(fin - deb == 1)
        return i - M;
    if(node[i*2].nbCl < val)
        return getId(i*2+1, mid, fin, val - node[i*2].nbCl);
    return getId(i*2, deb, mid, val);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> q;
    for(int i = 0; i < q; i++) {
        int typ; cin >> typ;
        ans[i] = -INF;
        if(typ == 1) {
            int l, r, c, k;
            cin >> l >> r >> c >> k;
            l--;
            id[i] = c;
            req[l].push_back({true, i, k, 0});
            req[r].push_back({true, -i-1, -k, 0});
        } else if(typ == 2) {
            int l, r, k;
            cin >> l >> r >> k;
            l--;
            req[l].push_back({true, i, -k, 0});
            req[r].push_back({true, -i-1, k, 0});
        } else {
            int a, b;
            cin >> a >> b;
            a--;
            req[a].push_back({false, i, 0, b});
        }
    }

    for(int i = 0; i < n; i++) {
        for(Req query : req[i]) {
            if(query.isUpd) {
                if(query.id >= 0) {
                    if(query.add > 0)
                        addFin(query.id, query.add);
                    else
                        dimLen(query.id, query.add);
                } else {
                    if(query.add < 0)
                        addFin(-query.id-1, query.add);
                    else
                        dimLen(-query.id-1, query.add);
                }
            } else {
                int fin = getVal(query.id),
                    len = getLen(query.id);
                if(len < query.req)
                    ans[query.id] = 0;
                else {
                    ans[query.id] = id[getId(1, 0, M, fin - len + query.req)];
                }
            }
        }
    }
    for(int i = 0; i < q; i++)
        if(ans[i] != -INF)
            cout << ans[i] << '\n';
}

• 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