Submission #421796

#	Time	Username	Problem	Language	Result	Execution time	Memory
421796		shenxy	Food Court (JOI21_foodcourt)	C++11	14 / 100	1077 ms	97208 KiB

foodcourt

#include <cstdio>
#include <algorithm>
#include <vector>
#define m (s+e)/2
using namespace std;
typedef pair<long long, 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(long long k) {
		prop();
		if (s == e) return s;
		if (r -> lazy + r -> v < k) return r -> descend(k);
		return l -> descend(k);
	}
} *r1, *r2;
struct dnc {
	int s, e;
	vector<int> ops;
	dnc *l, *r;
	dnc(int _s, int _e) {
		s = _s, e = _e;
		if (s != e) {
			l = new dnc(s, m);
			r = new dnc(m + 1, e);
		}
	}
	void update(int a, int b, int i) {
		if (s != a || e != b) {
			if (a > m) r -> update(a, b, i);
			else if (b <= m) l -> update(a, b, i);
			else l -> update(a, m, i), r -> update(m + 1, b, i);
		} else ops.push_back(i);
	}
	void query() {
		for (int i: ops) {
			if (T[i] == 3) {
				long long curr = r1 -> query(i, i) - r1 -> query(0, i);
				int l = 0, r = i;
				while (l != r) {
					int x = (l + r) / 2 + 1;
					if (r2 -> query(x, x) < r2 -> query(i, i) - curr + K[i]) l = x;
					else r = x - 1;
				}
				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]);
		}
		if (s != e) {
			l -> query();
			r -> query();
		}
		for (int i: ops) {
			if (T[i] == 1) r1 -> update(i, Q, -K[i]), r2 -> update(i, Q, -K[i]);
			else if (T[i] == 2) r1 -> update(i, Q, K[i]);
		}
	}
} *dc;
int main() {
	scanf("%d %d %d", &N, &M, &Q);
	r1 = new seg(0, Q);
	r2 = new seg(0, Q);
	dc = new dnc(1, N);
	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];
		dc -> update(L[i], R[i], i);
	}
	dc -> query();
	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:99:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |  scanf("%d %d %d", &N, &M, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   scanf("%d", &T[i]);
      |   ~~~~~^~~~~~~~~~~~~
foodcourt.cpp:105:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |   if (T[i] == 1) scanf("%d %d %d %lld", &L[i], &R[i], &C[i], &K[i]);
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:106:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   else if (T[i] == 2) scanf("%d %d %lld", &L[i], &R[i], &K[i]);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:107:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |   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: 0 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11