oj.uz

Submission #802260

# Submission time Handle Problem Language Result Execution time Memory
802260 2023-08-02T11:20:00 Z Divane Food Court (JOI21_foodcourt) C++14
21 / 100
 340 ms 24628 KB 
/* In the name of GOD */

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second 
#define mk make_pair
typedef long long ll;
typedef long double ld;
typedef pair <long long, long long> pii;
const int N = 250012, SegN = (1 << 19);
const long long INF = 1e16 + 31;
pii lz[SegN];
ll t[N], l[N], r[N], c[N], x[N];
ll k[N];

void shift (int v) {
	ll x = lz[v].F, y = lz[v].S;
	lz[v << 1].F += x;
	lz[v << 1].S += x;
	lz[v << 1 | 1].F += x;
	lz[v << 1 | 1].S += x;
	lz[v << 1].S = max(lz[v << 1].S, y);
	lz[v << 1 | 1].S = max(lz[v << 1 | 1].S, y);
	lz[v] = mk(0, -INF);
}

void mx (int l, int r, ll x, int v = 1, int tl = 0, int tr = N - 1) {
	if (tl > r || l > tr) 
		return;
	if (l <= tl && tr <= r) {
		lz[v].S = max(lz[v].S, x);
	} else {
		shift(v);
		int mid = (tl + tr) >> 1;
		mx (l, r, x, v << 1, tl, mid);
		mx (l, r, x, v << 1 | 1, mid + 1, tr);
	}
}

void add (int l, int r, ll x, int v = 1, int tl = 0, int tr = N - 1) {
//	cout << l << ' ' << r << ' ' << x << ' ' << v << ' ' << tl << ' ' << tr << '\n';
	if (tl > r || l > tr) 
		return;
	if (l <= tl && tr <= r) {
		//cout << "wef\n";
		lz[v].S += x;
		lz[v].F += x;
		//cout << lz[v].F << ' ' << lz[v].S << '\n';
	} else {
		shift(v);
		int mid = (tl + tr) >> 1;
		add (l, r, x, v << 1, tl, mid);
		add (l, r, x, v << 1 | 1, mid + 1, tr);
	}
}

pii get (int i, int v = 1, int tl = 0, int tr = N - 1) {
	if (tl == tr) 
		return lz[v];
	shift(v);
	int mid = (tl + tr) >> 1;
	if (i <= mid)
		return get (i, v << 1, tl, mid);
	return get (i, v << 1 | 1, mid + 1, tr);
}

int32_t main () {
	ios::sync_with_stdio(false);
	cin.tie();
	for (int v = 0; v < SegN; v++)
		lz[v] = mk(0, -INF);
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 0; i < q; i++) {
		cin >> t[i];
		if (t[i] == 1) {
			cin >> l[i] >> r[i] >> c[i] >> k[i];
			add (l[i], r[i], k[i]);
		} else if (t[i] == 2) {
			cin >> l[i] >> r[i] >> k[i]; 
			add (l[i], r[i], -k[i]);
			mx (l[i], r[i], 0);
		} else {
			cin >> l[i] >> k[i];
			pii p = get (l[i]);
			cout << (max(p.F, p.S) >= k[i]) << '\n';
		}
	}
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 22968 KB Output is correct
2 Correct 224 ms 20016 KB Output is correct
3 Correct 293 ms 24300 KB Output is correct
4 Correct 197 ms 20116 KB Output is correct
5 Correct 196 ms 20276 KB Output is correct
6 Correct 296 ms 24628 KB Output is correct
7 Correct 194 ms 22508 KB Output is correct
8 Correct 225 ms 22540 KB Output is correct
9 Correct 308 ms 24608 KB Output is correct
10 Correct 340 ms 24628 KB Output is correct
11 Correct 289 ms 23576 KB Output is correct
12 Correct 284 ms 24532 KB Output is correct
13 Correct 281 ms 23504 KB Output is correct
14 Correct 265 ms 24420 KB Output is correct
15 Correct 268 ms 24408 KB Output is correct
16 Correct 296 ms 24316 KB Output is correct
17 Correct 280 ms 24328 KB Output is correct
18 Correct 298 ms 24120 KB Output is correct
19 Correct 268 ms 24508 KB Output is correct
20 Correct 263 ms 23964 KB Output is correct
21 Correct 270 ms 24416 KB Output is correct
22 Correct 292 ms 24360 KB Output is correct
23 Correct 282 ms 24444 KB Output is correct
24 Correct 274 ms 24348 KB Output is correct
25 Correct 251 ms 23848 KB Output is correct
26 Correct 285 ms 24140 KB Output is correct
27 Correct 196 ms 24184 KB Output is correct

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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