Submission #652903

#	Time	Username	Problem	Language	Result	Execution time	Memory
652903		flappybird	Food Court (JOI21_foodcourt)	C++17	68 / 100	1053 ms	75536 KiB

foodcourt

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 251010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
struct node {
	ll a, b;
	node() :a(0), b(0) {}
	node(ll a) :a(min(a, 0ll)), b(a) {}
	node(ll a, ll b) :a(a), b(b) {}
};
node operator+(node& n1, node& n2) {
	node ret;
	ret.a = min(n1.a, n1.b + n2.a);
	ret.b = n1.b + n2.b;
	return ret;
}
void operator+= (node& n1, node& n2) { n1 = n1 + n2; }
void operator+=(node& n1, ll x) {
	n1.b += x;
	n1.a = min(n1.a, n1.b);
}
void operator+=(ll& x, node n1) {
	x += n1.a;
	ll ub = n1.b - n1.a;
	x = max(x, 0ll);
	x += ub;
}
typedef pair<int, ll> T;
struct segtree {
	vector<vector<T>> tree;
	vector<node> lazy;
	vector<int> l, r;
	vector<ll> rcnt;
	int s;
	int qcnt = 0;
	void init(int x = 1) {
		if (x >= s) {
			l[x] = r[x] = x - s + 1;
			return;
		}
		init(x * 2);
		init(x * 2 + 1);
		l[x] = l[x * 2];
		r[x] = r[x * 2 + 1];
	}
	segtree(int N = 0) {
		s = 1 << (int)ceil(log2(N));
		tree = vector<vector<T>>(2 * s + 1, vector<T>(1, T(0, 0ll)));
		lazy.resize(2 * s + 1);
		l.resize(2 * s + 1);
		r.resize(2 * s + 1);
		rcnt.resize(2 * s + 1);
		init();
	}
	void add(int low, int high, int t, int num, int loc = 1) {
		if (low == l[loc] && high == r[loc]) {
			tree[loc].emplace_back(t, num + tree[loc].back().second);
			return;
		}
		if (high <= r[loc * 2]) add(low, high, t, num, loc * 2);
		else if (low >= l[loc * 2 + 1]) add(low, high, t, num, loc * 2 + 1);
		else add(low, r[loc * 2], t, num, loc * 2), add(l[loc * 2 + 1], high, t, num, loc * 2 + 1);
	}
	void prop(int loc) {
		if (loc >= s) return;
		for (auto c : { loc * 2, loc * 2 + 1 }) {
			rcnt[c] += lazy[loc];
			lazy[c] += lazy[loc];
		}
		lazy[loc] = node();
	}
	void updnt(int low, int high, node num, int loc = 1) {
		prop(loc);
		if (low == l[loc] && high == r[loc]) {
			rcnt[loc] += num;
			lazy[loc] += num;
			return;
		}
		if (high <= r[loc * 2]) updnt(low, high, num, loc * 2);
		else if (low >= l[loc * 2 + 1]) updnt(low, high, num, loc * 2 + 1);
		else updnt(low, r[loc * 2], num, loc * 2), updnt(l[loc * 2 + 1], high, num, loc * 2 + 1);
		rcnt[loc] = min(rcnt[loc * 2], rcnt[loc * 2 + 1]);
	}
	ll getrcnt(int x, int loc = 1) {
		prop(loc);
		if (l[loc] == r[loc]) return rcnt[loc];
		if (x <= r[loc * 2]) return getrcnt(x, loc * 2);
		else return getrcnt(x, loc * 2 + 1);
	}
	ll gettcnt(int x, int t, int loc = 1) {
		int ind = upper_bound(tree[loc].begin(), tree[loc].end(), T(t + 1, -1)) - tree[loc].begin();
		ind--;
		ll ans;
		if (ind < 0) ans = 0;
		else ans = tree[loc][ind].second;
		if (l[loc] == r[loc]) return ans;
		if (x <= r[loc * 2]) return ans + gettcnt(x, t, loc * 2);
		else return ans + gettcnt(x, t, loc * 2 + 1);
	}
	void update(int l, int r, int t, int n) {
		add(l, r, t, n);
		updnt(l, r, node(n));
		qcnt++;
	}
	void remove(int l, int r, int n) { qcnt++; updnt(l, r, node(-n)); }
	int query(int A, ll B) {
		qcnt++;
		ll nb = B + (gettcnt(A, qcnt) - getrcnt(A));
		int l, r;
		if (gettcnt(A, qcnt) < nb) return -1;
		l = 0, r = qcnt;
		while (r - l > 1) {
			int mid = (l + r + 1) / 2;
			if (gettcnt(A, mid) < nb) l = mid;
			else r = mid;
		}
		return r;
	}
};
int cn[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, Q;
	cin >> N >> Q >> Q;
	segtree seg(N);
	int i;
	int t, l, r, c, k, a;
	ll b;
	for (i = 1; i <= Q; i++) {
		cin >> t;
		if (t == 1) cin >> l >> r >> c >> k, seg.update(l, r, i, k), cn[i] = c;
		if (t == 2) cin >> l >> r >> k, seg.remove(l, r, k);
		if (t == 3) {
			cin >> a >> b;
			int res = seg.query(a, b);
			if (!~res) cout << 0 << ln;
			else cout << cn[res] << ln;
		}
	}
}

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