oj.uz

답안 #421916

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
421916 2021-06-09T13:42:55 Z pavement 푸드 코트 (JOI21_foodcourt) C++17
0 / 100
 781 ms 172360 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, curq, out[100005];
ll B, ft[250005];
vector<iiii> q1;

struct node {
	node *left, *right;
	int S, E;
	bool hasmx;
	ll val, pv, pmx;
	node(int _s, int _e) : S(_s), E(_e), hasmx(0), val(0), pv(0), pmx(LLONG_MIN) {
		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) {
			pv += x;
			if (hasmx) pmx += x;
		} else {
			pmx = max(pmx, x);
			hasmx = 1;
		}
	}
	void prop() {
		if (S == E) return;
		left->val += pv;
		right->val += pv;
		left->add_prop(0, pv);
		right->add_prop(0, pv);
		pv = 0;
		if (hasmx) {
			left->val = max(left->val, pmx);
			right->val = max(right->val, pmx);
			left->add_prop(1, pmx);
			right->add_prop(1, pmx);
			pmx = LLONG_MIN;
		} else assert(pmx == LLONG_MIN);
		hasmx = 0;
	}
	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;

inline int ls(int x) { return x & -x; }

void upd(int l, int r, int v) {
	for (; l <= N; l += ls(l)) ft[l] += v;
	for (r++; r <= N; r += ls(r)) ft[r] -= v;
}

int qry(int p) {
	int r = 0;
	for (; p; p -= ls(p)) r += ft[p];
	return r;
}

struct node2 {
	node2 *left, *right;
	int S, E, pos;
	ll pv;
	vector<pair<ll, int> > val;
	tuple<ll, int, int> mv;
	node2(int _s, int _e) : S(_s), E(_e), pos(0), pv(0) {
		mv = mt(LLONG_MAX, -1, -1);
		if (S == E) return;
		int M = (S + E) >> 1;
		left = new node2(S, M);
		right = new node2(M + 1, E);
	}
	void prop() {
		if (S == E || !pv) return;
		g0(left->mv) += pv;
		left->pv += pv;
		g0(right->mv) += pv;
		right->pv += pv;
		pv = 0;
	}
	void upd(int p, int a, int b) {
		if (S == E) {
			val.eb(a, b);
			return;
		}
		int M = (S + E) >> 1;
		prop();
		if (p <= M) left->upd(p, a, b);
		else right->upd(p, a, b);
		mv = min(left->mv, right->mv);
	}
	void add(int l, int r, int v) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			g0(mv) += v;
			pv += v;
			return;
		}
		prop();
		left->add(l, r, v);
		right->add(l, r, v);
		mv = min(left->mv, right->mv);
	}
	void sortall() {
		if (S == E) {
			sort(val.begin(), val.end());
			if (!val.empty()) mv = mt(val[0].first, S, val[0].second);
			return;
		}
		prop();
		left->sortall();
		right->sortall();
		mv = min(left->mv, right->mv);
	}
	void del(int p) {
		if (S == E) {
			assert(pos < val.size());
			pos++;
			if (pos < val.size()) mv = mt(val[pos].first, S, val[pos].second);
			else mv = mt(LLONG_MAX, -1, -1);
			return;
		}
		int M = (S + E) >> 1;
		prop();
		if (p <= M) left->del(p);
		else right->del(p);
		mv = min(left->mv, right->mv);
	}
} *root2;

main() {
	read(N);
	read(M);
	read(Q);
	root = new node(1, N);
	root2 = new node2(1, N);
	for (int i = 1; i <= Q; i++) {
		read(T);
		if (T == 1) {
			read(L);
			read(R);
			read(C);
			read(K);
			q1.eb(L, R, C, K);
			root->add(L, R, K);
			upd(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);
			curq++;
			ll sz = root->qry(A), tmp = qry(A);
			if (sz >= B) root2->upd(A, tmp - (sz - B), curq);
		}
	}
	root2->sortall();
	for (auto [L, R, C, K] : q1) {
		root2->add(L, R, -K);
		while (g0(root2->mv) <= 0) {
			out[g2(root2->mv)] = C;
			root2->del(g1(root2->mv));
		}
	}
	for (int i = 1; i <= curq; i++) printf("%d\n", out[i]);
}

Compilation message

In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
                 from foodcourt.cpp:2:
foodcourt.cpp: In member function 'void node2::del(int)':
foodcourt.cpp:174:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |    assert(pos < val.size());
      |           ~~~~^~~~~~~~~~~~
foodcourt.cpp:176:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |    if (pos < val.size()) mv = mt(val[pos].first, S, val[pos].second);
      |        ~~~~^~~~~~~~~~~~
foodcourt.cpp: At global scope:
foodcourt.cpp:188:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  188 | main() {
      | ^~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 21916 KB Output is correct
2 Correct 109 ms 22036 KB Output is correct
3 Incorrect 101 ms 21960 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 639 ms 75908 KB Output is correct
2 Correct 503 ms 65512 KB Output is correct
3 Correct 747 ms 84364 KB Output is correct
4 Correct 601 ms 82980 KB Output is correct
5 Correct 591 ms 63632 KB Output is correct
6 Correct 781 ms 84476 KB Output is correct
7 Correct 38 ms 3632 KB Output is correct
8 Correct 46 ms 4056 KB Output is correct
9 Runtime error 691 ms 172360 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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