Submission #421819

#	Time	Username	Problem	Language	Result	Execution time	Memory
421819		shenxy	Food Court (JOI21_foodcourt)	C++11	68 / 100	1075 ms	52928 KiB

foodcourt

#include <cstdio>
#include <algorithm>
#include <vector>
#define m (s+e)/2
using namespace std;
typedef pair<int, int> ii;
int N, M, Q, T[250001], L[250001], R[250001], C[250001], ans[250001];
long long K[250001];
struct seg {
	int s, e;
	long long lazy, v;
	seg *l, *r;
	seg(int _s, int _e) {
		s = _s, e = _e;
		lazy = 0;
		v = 0;
		if (s != e) {
			l = new seg(s, m);
			r = new seg(m + 1, e);
		}
	}
	void prop() {
		if (lazy) {
			v += lazy;
			if (s != e) {
				l -> lazy += lazy;
				r -> lazy += lazy;
			}
			lazy = 0;
		}
	}
	void update(int a, int b, long long dv) {
		if (s != a || e != b) {
			if (a > m) r -> update(a, b, dv);
			else if (b <= m) l -> update(a, b, dv);
			else l -> update(a, m, dv), r -> update(m + 1, b, dv);
			l -> prop(), r -> prop();
			v = min(l -> v, r -> v);
		} else lazy += dv;
	}
	long long query(int a, int b) {
		prop();
		if (s == a && e == b) return v;
		if (a > m) return r -> query(a, b);
		if (b <= m) return l -> query(a, b);
		return min(l -> query(a, m), r -> query(m + 1, b));
	}
	int descend(int i, long long k) {
		prop();
		if (s == e) return s;
		if (m < i && r -> lazy + r -> v < k) return r -> descend(i, k);
		return l -> descend(i, k);
	}
} *r1, *r2;
int main() {
	scanf("%d %d %d", &N, &M, &Q);
	r1 = new seg(0, Q);
	r2 = new seg(0, Q);
	vector<ii> ops;
	for (int i = 1; i <= Q; ++i) {
		scanf("%d", &T[i]);
		if (T[i] == 1) scanf("%d %d %d %lld", &L[i], &R[i], &C[i], &K[i]);
		else if (T[i] == 2) scanf("%d %d %lld", &L[i], &R[i], &K[i]);
		else scanf("%d %lld", &L[i], &K[i]), R[i] = L[i];
		ops.push_back(ii(L[i], i));
		if (R[i] != N && T[i] != 3) ops.push_back(ii(R[i] + 1, -i));
	}
	sort(ops.begin(), ops.end());
	for (ii h: ops) {
		int i = h.second;
		if (i < 0 && T[-i] == 1) r1 -> update(-i, Q, -K[-i]), r2 -> update(-i, Q, -K[-i]);
		else if (i < 0 && T[-i] == 2) r1 -> update(-i, Q, K[-i]);
		else if (T[i] == 3) {
			long long curr = r1 -> query(i, i) - r1 -> query(0, i);
			int l = r2 -> descend(i, r2 -> query(i, i) - curr + K[i]);
			if (l == i) ans[i] = 0;
			else ans[i] = C[l + 1];
		} else if (T[i] == 1) r1 -> update(i, Q, K[i]), r2 -> update(i, Q, K[i]);
		else r1 -> update(i, Q, -K[i]);
	}
	for (int i = 1; i <= Q; ++i) {
		if (T[i] == 3) printf("%d\n", ans[i]);
	}
	return 0;
}

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf("%d %d %d", &N, &M, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   scanf("%d", &T[i]);
      |   ~~~~~^~~~~~~~~~~~~
foodcourt.cpp:62:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   if (T[i] == 1) scanf("%d %d %d %lld", &L[i], &R[i], &C[i], &K[i]);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:63:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |   else if (T[i] == 2) scanf("%d %d %lld", &L[i], &R[i], &K[i]);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:64:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   else scanf("%d %lld", &L[i], &K[i]), R[i] = L[i];
      |        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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