Submission #437205

#	Time	Username	Problem	Language	Result	Execution time	Memory
437205		maomao90	Food Court (JOI21_foodcourt)	C++17	100 / 100	668 ms	43460 KiB

foodcourt

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

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) _debug(args)
void _debug(const char* format, ...) {
	va_list args;
	va_start(args, format);
	vprintf(format, args);
	va_end(args);
}
#else
#define debug(args...)
#endif

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 300005

struct event {
	int v, i, t;
};
struct query {
	ll v;
   	int i;
};

int n, m, q;
vector<event> events[MAXN];
vector<query> queries[MAXN];
int grp[MAXN], ans[MAXN];

namespace st {
#define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
	ll mn[MAXN * 4], lazy[MAXN * 4];
	void propo(int u, int lo, int hi) {
		if (lazy[u] == 0 || lo == hi) return;
		MLR;
		lazy[lc] += lazy[u];
		lazy[rc] += lazy[u];
		mn[lc] += lazy[u];
		mn[rc] += lazy[u];
		lazy[u] = 0;
	}
	void incre(int s, int e, int x, int u = 1, int lo = 0, int hi = q) {
		if (lo >= s && hi <= e) {
			lazy[u] += x;
			mn[u] += x;
			return;
		}
		propo(u, lo, hi);
		MLR;
		if (s <= mid) {
			incre(s, e, x, lc, lo, mid);
		}
		if (e > mid) {
			incre(s, e, x, rc, mid + 1, hi);
		}
		mn[u] = min(mn[lc], mn[rc]);
	}
	ll qmn(int s, int e, int u = 1, int lo = 0, int hi = q) {
		if (lo >= s && hi <= e) {
			return mn[u];
		}
		propo(u, lo, hi);
		MLR;
		if (e <= mid) {
			return qmn(s, e, lc, lo, mid);
		} else if (s > mid) {
			return qmn(s, e, rc, mid + 1, hi);
		} else {
			return min(qmn(s, e, lc, lo, mid), qmn(s, e, rc, mid + 1, hi));
		}
	}
}

namespace fw {
	ll v[MAXN];
	void incre(int i, int x) {
		for (; i <= q; i += i & -i) v[i] += x;
	}
	ll qsm(int i) {
		ll res = 0;
		for (; i > 0; i -= i & -i) res += v[i];
		return res;
	}
	int get(ll x) {
		int id = 0;
		RREP (k, 25, 0) {
			id ^= (1 << k);
			if (id > q || v[id] >= x) {
				id ^= (1 << k);
			} else {
				x -= v[id];
			}
		}
		id++;
		return id;
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &q);
	memset(ans, -1, sizeof ans);
	REP (i, 1, q + 1) {
		int t; scanf("%d", &t);
		if (t == 1) {
			int l, r, c, k; scanf("%d%d%d%d", &l, &r, &c, &k);
			events[l].pb({k, i, 0});
			events[r + 1].pb({-k, i, 0});
			grp[i] = c;
		} else if (t == 2) {
			int l, r, k; scanf("%d%d%d", &l, &r, &k);
			events[l].pb({-k, i, 1});
			events[r + 1].pb({k, i, 1});
		} else {
			int a; ll b; scanf("%d%lld", &a, &b);
			queries[a].pb({b, i});
		}
	}
	REP (i, 1, n + 1) {
		debug("%d:\n", i);
		for (event &e : events[i]) {
			auto [v, i, t] = e;
			st::incre(i, q, v);
			debug(" st: %d to %d + %d\n", i, q, v);
			if (!t) {
				fw::incre(i, v);
				debug(" fw: %d + %d\n", i, v);
			}
		}
		for (query q : queries[i]) {
			auto [v, i] = q;
			debug(" %d %d\n", v, i);
			ll rem = st::qmn(i, i) - st::qmn(0, i);
			ll tot = fw::qsm(i);
			ll rmv = tot - rem;
			debug("  %lld %lld %lld\n", rem, tot, rmv);
			v += rmv;
			if (v > tot) {
				ans[i] = 0;
			} else {
				int id = fw::get(v);
				ans[i] = grp[id];
			}
		}
	}
	REP (i, 1, q + 1) {
		if (ans[i] == -1) continue;
		printf("%d\n", ans[i]);
	}
	return 0;
}

Compilation message (stderr)

foodcourt.cpp: In function 'void st::propo(int, int, int)':
foodcourt.cpp:56:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
      |                       ~~~^~~~
foodcourt.cpp:60:3: note: in expansion of macro 'MLR'
   60 |   MLR;
      |   ^~~
foodcourt.cpp:56:17: warning: unused variable 'mid' [-Wunused-variable]
   56 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
      |                 ^~~
foodcourt.cpp:60:3: note: in expansion of macro 'MLR'
   60 |   MLR;
      |   ^~~
foodcourt.cpp: In function 'void st::incre(int, int, int, int, int, int)':
foodcourt.cpp:56:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
      |                       ~~~^~~~
foodcourt.cpp:74:3: note: in expansion of macro 'MLR'
   74 |   MLR;
      |   ^~~
foodcourt.cpp: In function 'll st::qmn(int, int, int, int, int)':
foodcourt.cpp:56:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
      |                       ~~~^~~~
foodcourt.cpp:88:3: note: in expansion of macro 'MLR'
   88 |   MLR;
      |   ^~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:128:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |   int t; scanf("%d", &t);
      |          ~~~~~^~~~~~~~~~
foodcourt.cpp:130:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |    int l, r, c, k; scanf("%d%d%d%d", &l, &r, &c, &k);
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:135:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |    int l, r, k; scanf("%d%d%d", &l, &r, &k);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:139:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |    int a; ll b; scanf("%d%lld", &a, &b);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~

• 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