Submission #794191

#	Time	Username	Problem	Language	Result	Execution time	Memory
794191		ymm	Food Court (JOI21_foodcourt)	C++17	100 / 100	514 ms	56860 KiB

foodcourt

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
//typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

const int N = 250'010;
const ll inf = 1e18;

namespace beats {
	struct node {
		ll lzyadd, lzyaddmn;
		ll mn, mn2;
	} t[4*N];
	int sz;

	void up(int i, ll add, ll addmn) {
		t[i].lzyadd += add;
		t[i].mn += add;
		t[i].mn2 += add;
		t[i].lzyaddmn += addmn;
		t[i].mn += addmn;
	}
	void ppg(int i) {
		up(2*i+1, t[i].lzyadd, t[2*i+1].mn + t[i].lzyadd + t[i].lzyaddmn == t[i].mn? t[i].lzyaddmn: 0);
		up(2*i+2, t[i].lzyadd, t[2*i+2].mn + t[i].lzyadd + t[i].lzyaddmn == t[i].mn? t[i].lzyaddmn: 0);
		t[i].lzyadd = 0;
		t[i].lzyaddmn = 0;
	}
	void merge(int i) {
		node &v = t[i], &l = t[2*i+1], &r = t[2*i+2];
		v.mn = min(l.mn, r.mn);
		if (l.mn < r.mn)
			v.mn2 = min(l.mn2, r.mn);
		if (l.mn > r.mn)
			v.mn2 = min(l.mn, r.mn2);
		if (l.mn == r.mn)
			v.mn2 = min(l.mn2, r.mn2);
	}
	void init(int n) {
		sz = n;
		Loop (i,0,4*sz) {
			t[i].lzyadd = 0;
			t[i].lzyaddmn = 0;
			t[i].mn = 0;
			t[i].mn2 = inf;
		}
	}
	void add(int l, int r, ll x, int i, int b, int e) {
		if (l <= b && e <= r) {
			up(i, x, 0);
			return;
		}
		if (r <= b || e <= l)
			return;
		ppg(i);
		add(l, r, x, 2*i+1, b, (b+e)/2);
		add(l, r, x, 2*i+2, (b+e)/2, e);
		merge(i);
	}

	void mvup(int i, int b, int e) {
		if (t[i].mn >= 0)
			return;
		if (t[i].mn2 > 0) {
			up(i, 0, -t[i].mn);
			return;
		}
		ppg(i);
		mvup(2*i+1, b, (b+e)/2);
		mvup(2*i+2, (b+e)/2, e);
		merge(i);
	}

	void add(int l, int r, ll x) {
		add(l, r, x, 0, 0, sz);
		mvup(0, 0, sz);
	}

	ll get(int p, int i, int b, int e) {
		if (e-b == 1)
			return t[i].mn;
		ppg(i);
		if (p < (b+e)/2)
			return get(p, 2*i+1, b, (b+e)/2);
		else
			return get(p, 2*i+2, (b+e)/2, e);
	}
	ll get(int p) { return get(p, 0, 0, sz); }
}

namespace seg {
	struct node {
		ll cnt;
		int l, r;
	} nd[(1<<28)/sizeof(node)];
	int nxt = 1;
	vector<pair<int,int>> rts;
	int sz;

	void init(int n) {
		sz = n;
		rts = {{0,-1}};
	}
	int add(int t, int l, int r, ll x, int b, int e) {
		int ans = nxt++;
		if (l <= b && e <= r) {
			nd[ans].cnt = nd[t].cnt + x;
			nd[ans].l = nd[t].l;
			nd[ans].r = nd[t].r;
			return ans;
		}
		nd[ans] = nd[t];
		if (l < (b+e)/2)
			nd[ans].l = add(nd[t].l, l, r, x, b, (b+e)/2);
		if ((b+e)/2 < r)
			nd[ans].r = add(nd[t].r, l, r, x, (b+e)/2, e);
		return ans;
	}
	ll get(int t, int p, int b, int e) {
		if (!t)
			return 0;
		if (e-b == 1)
			return nd[t].cnt;
		if (p < (b+e)/2)
			return nd[t].cnt + get(nd[t].l, p, b, (b+e)/2);
		else
			return nd[t].cnt + get(nd[t].r, p, (b+e)/2, e);
	}
	void add(int l, int r, ll x, int c) {
		int rt = rts.back().first;
		int rt2 = add(rt, l, r, x, 0, sz);
		rts.push_back({rt2, c});
	}
	ll get(int p) { return get(rts.back().first, p, 0, sz); }
	int bin(int p, ll i) {
		int l = 1, r = rts.size()-1;
		while (l < r) {
			int m = (l+r)/2;
			if (get(rts[m].first, p, 0, sz) > i)
				r = m;
			else
				l = m+1;
		}
		return rts[l].second;
	}
}

namespace fen {
	ll a[N];
	void add(int r, ll x) {
		while (r > 0) {
			a[r] += x;
			r -= r&-r;
		}
	}
	void add(int l, int r, ll x) {
		add(r, x);
		add(l, -x);
	}
	ll get(int i) {
		++i;
		ll ans = 0;
		while (i < N) {
			ans += a[i];
			i += i&-i;
		}
		return ans;
	}
}

vector<tuple<ll,int,int,int>> Q;
vector<pair<ll,int>> Q2;
namespace pbs {
	int L[N], R[N];
	int ans[N];
	vector<int> vec[N];
	
	void Do() {
		memset(fen::a, 0, sizeof(fen::a));
		Loop (i,0,Q.size()) {
			auto [x, l, r, c] = Q[i];
			fen::add(l, r, x);
			for (int j : vec[i]) {
				auto [y, pos] = Q2[j];
				ans[j] = fen::get(pos) > y;
			}
			vec[i].clear();
		}
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int n, m, q;
	cin >> n >> m >> q;
	seg::init(n);
	beats::init(n);
	Loop (i,0,q) {
		int t;
		cin >> t;
		if (t == 1) {
			int l, r, c, k;
			cin >> l >> r >> c >> k;
			--l;
			Q.push_back({k,l,r,c});
			fen::add(l,r,k);
			beats::add(l, r, k);
		}
		if (t == 2) {
			int l, r, k;
			cin >> l >> r >> k;
			--l;
			beats::add(l, r, -k);
		}
		if (t == 3) {
			ll a, b;
			cin >> a >> b;
			--a; --b;
			ll cur = beats::get(a);
			ll tot = fen::get(a);
			b += tot - cur;
			pbs::L[Q2.size()] = 0;
			pbs::R[Q2.size()] = Q.size()-1;
			if (b >= tot)
				Q2.push_back({-1, -1});
			else
				Q2.push_back({b, a});
		}
	}
	Loop (_,0,20) {
		Loop (i,0,Q2.size()) {
			if (Q2[i].first == -1)
				continue;
			int l = pbs::L[i];
			int r = pbs::R[i];
			if (l == r)
				continue;
			int m = (l+r)/2;
			pbs::vec[m].push_back(i);
		}
		pbs::Do();
		Loop (i,0,Q2.size()) {
			if (Q2[i].first == -1)
				continue;
			int l = pbs::L[i];
			int r = pbs::R[i];
			if (l == r)
				continue;
			int m = (l+r)/2;
			if (pbs::ans[i])
				pbs::R[i] = m;
			else
				pbs::L[i] = m+1;
		}
	}
	Loop (i,0,Q2.size()) {
		if (Q2[i].first == -1)
			cout << "0\n";
		else
			cout << get<3>(Q[pbs::L[i]]) << '\n';
	}
}

Compilation message (stderr)

foodcourt.cpp: In function 'void pbs::Do()':
foodcourt.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::tuple<long long int, int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
foodcourt.cpp:183:3: note: in expansion of macro 'Loop'
  183 |   Loop (i,0,Q.size()) {
      |   ^~~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
foodcourt.cpp:235:3: note: in expansion of macro 'Loop'
  235 |   Loop (i,0,Q2.size()) {
      |   ^~~~
foodcourt.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
foodcourt.cpp:246:3: note: in expansion of macro 'Loop'
  246 |   Loop (i,0,Q2.size()) {
      |   ^~~~
foodcourt.cpp:2:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
foodcourt.cpp:260:2: note: in expansion of macro 'Loop'
  260 |  Loop (i,0,Q2.size()) {
      |  ^~~~

• 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