oj.uz

Submission #421850

# Submission time Handle Problem Language Result Execution time Memory
421850 2021-06-09T12:59:30 Z pavement Food Court (JOI21_foodcourt) C++17
0 / 100
 1000 ms 62692 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
//#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<iii, null_type, greater<iii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

void read(int &v) {
	v = 0;
	char ch = getchar_unlocked();
	for (; ch < '0' || ch > '9'; ch = getchar_unlocked());
	for (; '0' <= ch && ch <= '9'; ch = getchar_unlocked())
		v = (v << 3) + (v << 1) + (ch & 15);
}

void read(ll &v) {
	v = 0;
	char ch = getchar_unlocked();
	for (; ch < '0' || ch > '9'; ch = getchar_unlocked());
	for (; '0' <= ch && ch <= '9'; ch = getchar_unlocked())
		v = (v << 3ll) + (v << 1ll) + (ch & 15ll);
}

int N, M, Q, T, L, R, C, K, A;
ll B;

struct node {
	node *left, *right;
	int S, E;
	ll val, pv;
	vector<pair<bool, ll> > vec;
	node(int _s, int _e) : S(_s), E(_e), val(0), pv(0) {
		if (S == E) return;
		int M = (S + E) >> 1;
		left = new node(S, M);
		right = new node(M + 1, E);
	}
	void add_prop(bool t, ll x) {
		if (t == 0) {
			if (vec.empty()) vec.eb(t, x);
			else if (vec.back().first == 0) vec.back().second += x;
			else vec.back().second += x, pv += x;
		} else {
			if (vec.empty()) vec.eb(t, x);
			else if (vec.back().first == 1) vec.back().second = max(vec.back().second, x);
			else vec.eb(t, x);
		}
		assert(vec.size() <= 2);
	}
	void prop() {
		if (S == E) return;
		left->val += pv;
		right->val += pv;
		left->add_prop(0, pv);
		right->add_prop(0, pv);
		pv = 0;
		assert(vec.size() <= 2);
		if (vec.size() == 2) assert(vec[0].first == 0 && vec[1].first == 1);
		for (auto [t, x] : vec) {
			if (t == 0) {
				left->val += x;
				right->val += x;
			} else {
				left->val = max(left->val, x);
				right->val = max(right->val, x);
			}
			left->add_prop(t, x);
			right->add_prop(t, x);
		}
		vec.clear();
	}
	void add(int l, int r, ll v) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			add_prop(0, v);
			val += v;
			return;
		}
		prop();
		left->add(l, r, v);
		right->add(l, r, v);
	}
	ll qry(int p) {
		if (S == E) return val;
		int M = (S + E) >> 1;
		prop();
		if (p <= M) return left->qry(p);
		else return right->qry(p);
	}
} *root;

main() {
	read(N);
	read(M);
	read(Q);
	root = new node(1, N);
	for (int i = 1; i <= Q; i++) {
		read(T);
		if (T == 1) {
			read(L);
			read(R);
			read(C);
			read(K);
			root->add(L, R, K);
		} else if (T == 2) {
			read(L);
			read(R);
			read(K);
			root->add(L, R, -K);
			root->val = max(0ll, root->val);
			root->add_prop(1, 0);
		} else {
			read(A);
			read(B);
			printf("%d\n", (root->qry(A) >= B ? 1 : 0));
		}
	}
}

Compilation message

foodcourt.cpp:112:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  112 | main() {
      | ^~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 874 ms 55344 KB Output is correct
2 Correct 643 ms 47948 KB Output is correct
3 Correct 961 ms 61436 KB Output is correct
4 Correct 751 ms 59588 KB Output is correct
5 Correct 671 ms 46136 KB Output is correct
6 Correct 888 ms 61380 KB Output is correct
7 Correct 29 ms 1220 KB Output is correct
8 Correct 36 ms 1256 KB Output is correct
9 Correct 853 ms 62280 KB Output is correct
10 Correct 810 ms 62364 KB Output is correct
11 Correct 908 ms 62692 KB Output is correct
12 Correct 925 ms 62116 KB Output is correct
13 Correct 890 ms 62596 KB Output is correct
14 Correct 908 ms 62092 KB Output is correct
15 Correct 914 ms 62012 KB Output is correct
16 Correct 914 ms 62084 KB Output is correct
17 Correct 928 ms 62148 KB Output is correct
18 Correct 895 ms 62076 KB Output is correct
19 Correct 919 ms 62052 KB Output is correct
20 Correct 887 ms 62040 KB Output is correct
21 Execution timed out 1030 ms 61356 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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