Submission #426041

#	Time	Username	Problem	Language	Result	Execution time	Memory
426041		Kevin_Zhang_TW	Food Court (JOI21_foodcourt)	C++17	100 / 100	773 ms	44560 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
 
const int MAX_N = 300010;
const ll inf = 1ll << 60;
 
int n, m, q;
int res[MAX_N], cid[MAX_N];
 
bool is_leave[MAX_N];
 
//          position, delta
vector<pair<int,ll>> rec[MAX_N];
//         time, k
vector<pair<int,ll>> allq[MAX_N];
 
struct sgt {
	struct node {
		ll mn, pos, tg;
		void operator += (ll v) {
			mn += v, tg += v;
		}
		node (node a, node b) {
			tg = 0;
			mn = min(a.mn, b.mn);
			pos = a.mn == mn ? a.pos : b.pos;
		}
		node () : mn(0), pos(0), tg(0) {}
		pair<ll,ll> get() { return make_pair(mn, pos); }
	};
	int n;
	vector<node> val;
	sgt(int _n) {
		n = _n;
		val.resize(n<<1);
		for (int i = 0;i < n+n;++i) {
			assert(val[i].mn == 0 && val[i].pos == 0 && val[i].tg == 0);
		}
		for (int i = 0;i < n;++i)
			val[i+n].pos = i;
		for (int i = n-1;i > 0;--i)
			upd(i);
	}
	void pa(int j) { for (int i = 20;i >= 0;--i) push(j>>i); }
	void add(int l, int r, ll v) {
		assert(r == q);
		int sl = l+=n, sr = r+=n;
		pa(l), pa(r-1);
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) val[l++] += v;
			if (r&1) val[--r] += v;
		}
		for (--sr;sl>>=1, sr>>=1;) 
			upd(sl), upd(sr);
	}
	void push(int i) {
		if (i >= n) return;
		ll &t = val[i].tg;
		val[i<<1] += t, val[i<<1|1] += t;
		t = 0;
	}
	void upd(int i) {
		if (i >= n) return;
		push(i);
		val[i] = node(val[i<<1], val[i<<1|1]);
	}
	pair<ll,ll> qmn(int l, int r) {
		l += n, r += n;
		pa(l), pa(r-1);
		pair<ll,ll> res {inf, n};
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) chmin(res, val[l++].get());
			if (r&1) chmin(res, val[--r].get());
		}
		assert(res.first < inf);
		return res;
	} 
};
 
// t1 for +
// t2 for -
struct bit { 
	int n;
	vector<ll> val;
	bit (int n) : n(n) {
		val.resize(n);
	}
	void add(int i, ll v) {
		for (;i < n;i += i&-i)
			val[i] += v;
	}
	ll qry(int i) {
		ll res = 0;
		for (;i;i^=i&-i) res += val[i];
		return res;
	}
	ll qry(int l, int r) { return qry(r) - qry(l-1); }
	int kth(ll k) {
		int res = 0;
		for (int i = 1<<19;i > 0;i>>=1) {
			if ((i|res) >= n || k <= val[res|i]) continue;
			assert(k > val[res|i]);
			k -= val[res|=i];
		}
		assert(k > 0);
		return res + 1; 
	} 
};
 
struct sss {
	vector<ll> val;
	int n;
	sss (int n) : n(n) {
		val.resize(n);
	}
	void add(int l, int r, ll v) {
		for (;l < r;++l)
			val[l] += v;
	}
	pair<ll,ll> qmn(int l, int r) {
		pair<ll,ll> res {inf, n};
		for (;l < r;++l)
			chmin(res, make_pair(val[l], (ll)l));
		return res;
	}
};
void solve() {
 
	//sss tree(q);
	sgt tree(q);
	bit t1(q + 10), t2(q + 10);
 
	for (int i = 1;i <= n;++i) {
		for (auto [j, d] : rec[i]) {
			tree.add(j, q, d);
			if (is_leave[j]) 
				t2.add(j, -d);
			else {
				assert(cid[j]);
				t1.add(j, d);
			} 
		}
 
		for (auto [t, k] : allq[i]) {
			auto [v, p] = tree.qmn(0, t); 
 
			assert(p == 0 || is_leave[p]);
 
			assert(p < t);
 
			ll rk = t1.qry(p) + k + t2.qry(p+1, t);
 
			//assert(p == 0 || t1.qry(p) == t1.qry(p-1));
 
			assert(t1.qry(p) - t2.qry(p) == v);
 
			if (t1.qry(t) < rk) {
				res[t] = 0;
				continue;
			}
			
			int ind = t1.kth(rk);
			
			assert(ind < t);
			res[t] = cid[ind]; 
 
			assert(cid[ind] >= 1 && cid[ind] <= m);
		}
	} 
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> q; ++q;
 
	fill(res, res + q, -1);
 
	for (ll t, l, r, k, i = 1;i < q;++i) {
		cin >> t;
		if (t == 1) {
			cin >> l >> r >> cid[i] >> k;
			rec[l].pb(i, k);
			rec[r+1].pb(i,-k);
		}
		if (t == 2) {
			cin >> l >> r >> k;
			is_leave[i] = true;
			rec[l].pb(i, -k);
			rec[r+1].pb(i, k);
		}
		if (t == 3) {
			cin >> l >> k;
			allq[l].pb(i, k);
		}
	}
 
	solve();
 
	for (int i = 0;i < q;++i) {
		if (res[i] == -1) continue;
		cout << res[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