Submission #1288845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288845		thieunguyenhuy	Food Court (JOI21_foodcourt)	C++20	100 / 100	373 ms	27768 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;

#define POPCOUNT(n) (__builtin_popcountll((n)))
#define CLZ(n) (__builtin_clzll((n)))
#define CTZ(n) (__builtin_ctzll((n)))
#define LOG(n) (63 - __builtin_clzll((n)))
#define BIT(n, i) (((n) >> (i)) & 1ll)
#define MASK(i) (1ll << (i))
#define FLIP(n, i) ((n) ^ (1ll << (i)))
#define ON(n, i) ((n) | MASK(i))
#define OFF(n, i) ((n) & ~MASK(i))

#define Int __int128
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long long, int> pli;
typedef pair<int, long long> pil;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long, long long>> vll;
typedef vector<pair<long long, int>> vli;
typedef vector<pair<int, long long>> vil;

template <class T1, class T2> bool maximize(T1 &x, T2 y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <class T1, class T2> bool minimize(T1 &x, T2 y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template <class T> void remove_duplicate(vector<T> &ve) {
    sort (ve.begin(), ve.end());
    ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
}

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long random(long long l, long long r) {
    return uniform_int_distribution<long long>(l, r)(rng);
}
unsigned long long random(unsigned long long l, unsigned long long r) {
    return uniform_int_distribution<unsigned long long>(l, r)(rng);
}
template <class T> T random(T r) {
    return rng() % r;
}

const int N = 25e4 + 5, LG = 19;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const long long INF = 1e18;

int n, m, q;
int low[N], high[N], ans[N];

struct SegmentTreeBeats {
    struct Node
    {
        ll cap, add;

        Node() : cap(0), add(0) {};
    };
    vector<Node> st;
    int n;

    SegmentTreeBeats(int n) : n(n) { st.resize(4 * n + 1); }

    void apply(int head, ll c, ll a)
    {
        st[head].cap = min(st[head].cap + a, c);
        st[head].add += a;
    }

    void pass(int head)
    {
        apply(head << 1, st[head].cap, st[head].add);
        apply(head << 1 | 1, st[head].cap, st[head].add);
        st[head].cap = INF;
        st[head].add = 0;
    }

    void update(int head, int l, int r, int u, int v, ll val)
    {
        if (l > v || r < u) return;
        if (u <= l && r <= v)
        {
            apply(head, INF, val);
            return;
        }
        pass(head);
        int mid = l + r >> 1;
        update(head << 1, l, mid, u, v, val);
        update(head << 1 | 1, mid + 1, r, u, v, val);
    }
    void update(int u, int v, ll val)
    {
        update(1, 1, n, u, v, val);
        apply(1, 0, 0);
    }

    ll get(int head, int l, int r, int pos)
    {
        if (pos < l || r < pos) return -INF;
        if (l == r) return st[head].cap;
        pass(head);
        int mid = l + r >> 1;
        return max(get(head << 1, l, mid, pos), get(head << 1 | 1, mid + 1, r, pos));
    }
    ll get(int pos) { return get(1, 1, n, pos); }
};

struct FenwickTree {
    using T = long long;
    vector<T> bit;

    FenwickTree(int n) {
    	resize(n);
    }

    void resize(int n) {
        bit.assign(n + 1, 0);
    }

    void update(int p, T val) {
        for (; p < int(bit.size()); p += p & -p) bit[p] += val;
    }

	void update(int l, int r, T val) {
		update(l, val), update(r + 1, -val);
	}

    T get(int p) {
        T ans = 0;
        for (; p > 0; p -= p & -p) ans += bit[p];
        return ans;
    }
};

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m >> q;

    SegmentTreeBeats len(n);
    FenwickTree R(n);

    vector<tuple<int, int, int, int>> joins;
    vector<tuple<int, ll, int>> queries;
    memset(ans, -1, sizeof ans);

    for (int i = 1; i <= q; ++i) {
    	int type; cin >> type;
    	if (type == 1) {
    		int l, r, c, k; cin >> l >> r >> c >> k;
    		joins.emplace_back(l, r, c, k);
    		R.update(l, r, k);
    		len.update(l, r, -k);
    	}
    	if (type == 2) {
    		int l, r, k; cin >> l >> r >> k;
    		len.update(l, r, k);
    	}
    	if (type == 3) {
    		int x; ll k; cin >> x >> k;
    		ll rightId = R.get(x);
    		ll leftId = rightId + len.get(x);
    		if (leftId + k > rightId) ans[i] = 0;
    		else queries.emplace_back(x, leftId + k, i);
    	}
    }

    for (int i = 0; i < queries.size(); ++i) low[i] = 0, high[i] = joins.size() - 1;

    FenwickTree fen(n);
    while (true) {
    	vii ve;
    	for (int i = 0; i < queries.size(); ++i) {
    		auto [x, p, id] = queries[i];
    		if (low[i] <= high[i]) {
    			ve.emplace_back((low[i] + high[i]) >> 1, i);
    		}
    	}
    	if (ve.empty()) break;

    	sort (ve.begin(), ve.end());
    	fen.resize(n); int j = -1;
    	for (auto [mid, i] : ve) {
    		while (j < mid) {
    			auto [l, r, c, k] = joins[++j];
    			fen.update(l, r, k);
    		}

    		auto [x, p, id] = queries[i];
    		if (fen.get(x) >= p) {
    			high[i] = mid - 1;
    			ans[id] = get<2>(joins[mid]);
    		}
    		else low[i] = mid + 1;
    	}
    }

    for (int i = 1; i <= q; ++i) 
    	if (ans[i] != -1) cout << ans[i] << '\n';
    return 0;
}

• 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