oj.uz

답안 #421801

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
421801 2021-06-09T12:19:43 Z pavement 푸드 코트 (JOI21_foodcourt) C++17
0 / 100
 1000 ms 49564 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;

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

struct node {
	node *left, *right;
	int S, E;
	ll minval, sminval, pv;
	vector<pair<bool, ll> > vec;
	node(int _s, int _e) : S(_s), E(_e), minval(0), sminval(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);
		}
		assert(vec.size() <= 2);
	}
	void prop() {
		if (S == E) return;
		left->minval += pv;
		left->sminval += pv;
		right->minval += pv;
		right->sminval += 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->minval += x;
				left->sminval += x;
				right->minval += x;
				right->sminval += x;
				
			} else {
				left->minval = max(left->minval, x);
				assert(left->sminval > x);
				right->minval = max(right->minval, x);
				assert(right->sminval > x);
			}
			left->add_prop(t, x);
			right->add_prop(t, x);
		}
		pv = 0;
		vec.clear();
	}
	void combine() {
		if (left->minval == right->minval) {
			minval = left->minval;
			sminval = min(left->sminval, right->sminval);
		} else if (left->minval < right->minval) {
			minval = left->minval;
			sminval = min(left->sminval, right->minval);
		} else {
			minval = right->minval;
			sminval = min(left->minval, right->sminval);
		}
	}
	void add(int l, int r, int v) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			add_prop(0, v);
			minval += v;
			sminval += v;
			return;
		}
		if (S == E) {
			assert(minval == sminval);
			minval += v;
			sminval += v;
			return;
		}
		prop();
		left->add(l, r, v);
		right->add(l, r, v);
		combine();
	}
	void maxeq(int l, int r) {
		if (l > E || r < S || minval >= 0) return;
		if (l <= S && E <= r && sminval > 0) {
			minval = 0;
			add_prop(1, 0);
			return;
		}
		if (S == E) {
			assert(minval == sminval);
			minval = sminval = 0;
			return;
		}
		prop();
		left->maxeq(l, r);
		right->maxeq(l, r);
		combine();
	}
	int qry(int p) {
		if (S == E) return minval;
		int M = (S + E) >> 1;
		prop();
		if (p <= M) return left->qry(p);
		else return right->qry(p);
	}
} *root;

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M >> Q;
	root = new node(1, N);
	for (int i = 1; i <= Q; i++) {
		cin >> T;
		if (T == 1) {
			cin >> L >> R >> C >> K;
			root->add(L, R, K);
		} else if (T == 2) {
			cin >> L >> R >> K;
			root->add(L, R, -K);
			root->maxeq(L, R);
		} else {
			cin >> A >> B;
			cout << (root->qry(A) >= B ? 1 : 0) << '\n';
		}
	}
}

Compilation message

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

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1092 ms 14492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1086 ms 49564 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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