oj.uz

Submission #557192

# Submission time Handle Problem Language Result Execution time Memory
557192 2022-05-04T20:47:24 Z lunchbox Food Court (JOI21_foodcourt) C++17
7 / 100
 321 ms 36272 KB 
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const int N = 250000, N_ = 1 << 18, INF = 0x3f3f3f3f;

int n_;

array<LL, 2> st1[N_ * 2];

array<LL, 2> join(array<LL, 2> a, array<LL, 2> b) {
	return { a[0] + b[0], max(a[1] + b[0], b[1]) };
}

void update1(int i, int x) {
	i |= n_;
	st1[i][0] = x;
	st1[i][1] = max(0, x);
	while (i >>= 1)
		st1[i] = join(st1[i << 1 | 0], st1[i << 1 | 1]);
}

LL query1(int l, int r) {
	vector<int> ll, rr;
	array<LL, 2> v = { 0, 0 };

	for (l |= n_, r |= n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			ll.push_back(l++);
		if ((r & 1) == 0)
			rr.push_back(r--);
	}
	for (int i : ll)
		v = join(v, st1[i]);
	reverse(rr.begin(), rr.end());
	for (int i : rr)
		v = join(v, st1[i]);
	return v[1];
}

LL st2[N_ * 2], ll[N_ * 2];

void update2(int i, int x) {
	i |= n_;
	ll[i] = st2[i] = x;
	while (i >>= 1) {
		st2[i] = st2[i << 1 | 0] + st2[i << 1 | 1];
		ll[i] = ll[i << 1 | 0];
	}
}

LL query2(int l, int r) {
	LL sum = 0;

	for (l |= n_, r |= n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			sum += st2[l++];
		if ((r & 1) == 0)
			sum += st2[r--];
	}
	return sum;
}

int query3(LL x) {
	int i = 1;

	while (i < n_) {
		if (st2[i << 1 | 0] + ll[i << 1 | 1] < x) {
			x -= st2[i << 1 | 0];
			i = i << 1 | 1;
		} else
			i = i << 1 | 0;

	}
	return i ^ n_;
}

vector<pair<int, int>> uu[N], qq[N];

void run() {
	static int cc[N], ans[N];
	int n, m, q;

	scanf("%d%d%d", &n, &m, &q);
	n_ = 1;
	while (n_ < q)
		n_ <<= 1;
	for (int h = 0; h < q; h++) {
		int t;

		scanf("%d", &t);
		if (t == 1) {
			int l, r, k;

			scanf("%d%d%d%d", &l, &r, &cc[h], &k), l--;
			uu[l].push_back({ h << 1 | 0, k });
			uu[r].push_back({ h << 1 | 0, 0 });
		} else if (t == 2) {
			int l, r, k;

			scanf("%d%d%d", &l, &r, &k), l--;
			uu[l].push_back({ h << 1 | 1, -k });
			uu[r].push_back({ h << 1 | 1, 0 });
		} else {
			int i, k;

			scanf("%d%d", &i, &k), i--;
			qq[i].push_back({ h, k });
		}
	}
	memset(ans, -1, q * sizeof * ans);
	for (int i = 0; i < n; i++) {
		for (auto [h2, k] : uu[i]) {
			int h = h2 >> 1;

			update1(h, k);
			if ((h2 & 1) == 0)
				update2(h, k);
		}
		for (auto [h, k] : qq[i]) {
			LL x = query1(0, h);

			ans[h] = x < k ? 0 : cc[query3(query2(0, h) - x + k) + 1];
		}
	}
	for (int h = 0; h < q; h++)
		if (ans[h] != -1)
			printf("%d\n", ans[h]);
}

int main() {
	run();
	return 0;
}

Compilation message

foodcourt.cpp: In function 'void run()':
foodcourt.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   scanf("%d", &t);
      |   ~~~~~^~~~~~~~~~
foodcourt.cpp:95:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |    scanf("%d%d%d%d", &l, &r, &cc[h], &k), l--;
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:101:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |    scanf("%d%d%d", &l, &r, &k), l--;
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:107:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |    scanf("%d%d", &i, &k), i--;
      |    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 12244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 12244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 18928 KB Output is correct
2 Correct 69 ms 18868 KB Output is correct
3 Correct 68 ms 18892 KB Output is correct
4 Correct 60 ms 18836 KB Output is correct
5 Correct 61 ms 18940 KB Output is correct
6 Correct 67 ms 18916 KB Output is correct
7 Correct 38 ms 17452 KB Output is correct
8 Correct 39 ms 17516 KB Output is correct
9 Correct 58 ms 18068 KB Output is correct
10 Correct 60 ms 18892 KB Output is correct
11 Correct 61 ms 18636 KB Output is correct
12 Correct 61 ms 18928 KB Output is correct
13 Correct 53 ms 18084 KB Output is correct
14 Correct 68 ms 18864 KB Output is correct
15 Correct 61 ms 18640 KB Output is correct
16 Correct 64 ms 18860 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 321 ms 36272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 12244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 18308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 12244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 12244 KB Output isn't correct
2 Halted 0 ms 0 KB -