oj.uz

답안 #557193

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
557193 2022-05-04T20:48:03 Z lunchbox 푸드 코트 (JOI21_foodcourt) C++17
0 / 100
 345 ms 36356 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) + 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 12244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 12244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 97 ms 18864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 345 ms 36356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 12244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 18288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 12244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 12244 KB Output isn't correct
2 Halted 0 ms 0 KB -