oj.uz

Submission #955359

# Submission time Handle Problem Language Result Execution time Memory
955359 2024-03-30T08:21:23 Z Der_Vlapos Food Court (JOI21_foodcourt) C++17
21 / 100
 411 ms 36536 KB 
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #include <x86intrin.h>

#include <bits/stdc++.h>
#include <chrono>
#include <random>

// @author: Vlapos

namespace operators
{
	template <typename T1, typename T2>
	std::istream &operator>>(std::istream &in, std::pair<T1, T2> &x)
	{
		in >> x.first >> x.second;
		return in;
	}

	template <typename T1, typename T2>
	std::ostream &operator<<(std::ostream &out, std::pair<T1, T2> x)
	{
		out << x.first << " " << x.second;
		return out;
	}

	template <typename T1>
	std::istream &operator>>(std::istream &in, std::vector<T1> &x)
	{
		for (auto &i : x)
			in >> i;
		return in;
	}

	template <typename T1>
	std::ostream &operator<<(std::ostream &out, std::vector<T1> &x)
	{
		for (auto &i : x)
			out << i << " ";
		return out;
	}

	template <typename T1>
	std::ostream &operator<<(std::ostream &out, std::set<T1> &x)
	{
		for (auto &i : x)
			out << i << " ";
		return out;
	}
}

// name spaces
using namespace std;
using namespace operators;
// end of name spaces

// defines
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
#define uint unsigned int
#define all(vc) vc.begin(), vc.end()
// end of defines

// usefull stuff

void boost()
{
	ios_base ::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

inline int getbit(int &x, int &bt) { return (x >> bt) & 1; }

const int dx4[4] = {-1, 0, 0, 1};
const int dy4[4] = {0, -1, 1, 0};
const int dx8[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy8[8] = {-1, -0, 1, -1, 1, -1, 0, 1};

const ll INF = (1e17) + 500;
const int BIG = (1e9) * 2 + 100;
const int MAXN = (1e5) + 5;
const int MOD7 = (1e9) + 7;
const int MOD9 = (1e9) + 9;
const uint MODFFT = 998244353;

#define int ll

struct segTree
{
	struct Node
	{
		int mx = 0, op = 0;
	};
	vector<Node> tree;
	int sz = 0;

	void init(int n)
	{
		sz = 1;
		while (sz < n)
			sz *= 2;
		tree.resize(2 * sz);
	}

	void upd(int v, int val)
	{
		tree[v].op += val;
		tree[v].mx += val;
	}

	void push(int v, int lv, int rv)
	{
		if (rv - lv == 1 or tree[v].op == 0)
			return;
		upd(v * 2 + 1, tree[v].op);
		upd(v * 2 + 2, tree[v].op);
		tree[v].op = 0;
	}

	void updSeg(int l, int r, int val, int v, int lv, int rv)
	{
		push(v, lv, rv);
		if (l <= lv and rv <= r)
		{
			upd(v, val);
			return;
		}
		if (rv <= l or r <= lv)
			return;
		int m = (lv + rv) >> 1;
		updSeg(l, r, val, v * 2 + 1, lv, m);
		updSeg(l, r, val, v * 2 + 2, m, rv);
		tree[v].mx = max(tree[v * 2 + 1].mx, tree[v * 2 + 2].mx);
	}

	void updSeg(int l, int r, int val)
	{
		updSeg(l, r, val, 0, 0, sz);
	}

	int getPos(int pos, int v, int lv, int rv)
	{
		push(v, lv, rv);
		if (rv - lv == 1)
			return tree[v].mx;
		int m = (lv + rv) >> 1;
		if (pos < m)
			return getPos(pos, v * 2 + 1, lv, m);
		return getPos(pos, v * 2 + 2, m, rv);
	}

	int getPos(int pos)
	{
		return getPos(pos, 0, 0, sz);
	}

	int getGoodPos(int v, int lv, int rv)
	{
		push(v, lv, rv);
		if (rv - lv == 1)
			return lv;
		int m = (lv + rv) >> 1;
		if (tree[v * 2 + 1].mx >= 0)
			return getGoodPos(v * 2 + 1, lv, m);
		return getGoodPos(v * 2 + 2, m, rv);
	}

	int getGoodPos()
	{
		return getGoodPos(0, 0, sz);
	}
};

struct segTreeBF
{
	struct Node
	{
		int add = 0, del = 0;
	};
	vector<Node> tree;
	int sz = 0;

	void init(int n)
	{
		sz = 1;
		while (sz < n)
			sz *= 2;
		tree.resize(2 * sz);
	}

	void upd(int v, int val)
	{
		if (tree[v].add + val >= 0)
			tree[v].add = tree[v].add + val;
		else
		{
			tree[v].del += tree[v].add + val;
			tree[v].add = 0;
		}
	}

	void push(int v, int lv, int rv)
	{
		if (rv - lv == 1 or (tree[v].add == 0 and tree[v].del == 0))
			return;
		upd(v * 2 + 1, tree[v].del);
		upd(v * 2 + 1, tree[v].add);
		upd(v * 2 + 2, tree[v].del);
		upd(v * 2 + 2, tree[v].add);
		tree[v].add = tree[v].del = 0;
	}

	void updSeg(int l, int r, int val, int v, int lv, int rv)
	{
		push(v, lv, rv);
		if (l <= lv and rv <= r)
		{
			upd(v, val);
			return;
		}
		if (rv <= l or r <= lv)
			return;
		int m = (lv + rv) >> 1;
		updSeg(l, r, val, v * 2 + 1, lv, m);
		updSeg(l, r, val, v * 2 + 2, m, rv);
	}

	void updSeg(int l, int r, int val)
	{
		updSeg(l, r, val, 0, 0, sz);
	}

	int getPos(int pos, int v, int lv, int rv)
	{
		push(v, lv, rv);
		if (rv - lv == 1)
		{
			return tree[v].add;
		}
		int m = (lv + rv) >> 1;
		if (pos < m)
			return getPos(pos, v * 2 + 1, lv, m);
		return getPos(pos, v * 2 + 2, m, rv);
	}

	int getPos(int pos)
	{
		return getPos(pos, 0, 0, sz);
	}
};

struct test
{
	void solve(int testcase)
	{
		boost();
		int n, m, q;
		cin >> n >> m >> q;
		int cntA = 0;
		vector<vector<pair<pii, int>>> ops(n);

		vector<pair<pii, pii>> updates;
		segTreeBF bf1, bf2;
		vector<int> ans;
		bf1.init(n);
		bf2.init(n);
		for (int i = 0; i < q; ++i)
		{
			int tp;
			cin >> tp;
			if (tp == 1)
			{
				int l, r, c, k;
				cin >> l >> r >> c >> k;
				--l;
				updates.pb({{l, r}, {c, k}});
				bf1.updSeg(l, r, k);
				bf2.updSeg(l, r, k);
			}
			else if (tp == 2)
			{
				int l, r, k;
				cin >> l >> r >> k;
				--l;
				bf2.updSeg(l, r, -k);
			}
			else
			{
				int p, val;
				cin >> p >> val;
				--p;
				int cntLeave = bf1.getPos(p) - bf2.getPos(p);
				if (bf2.getPos(p) >= val)
				{
					ops[p].pb({{cntLeave, val}, cntA});
					ans.pb(1);
				}
				else
					ans.pb(0);
				cntA++;
			}
		}
		// for (int i = 0; i < n; ++i)
		//     ops[i].pb({{INF, INF}, BIG});
		// segTree res;
		// res.init(n + 1);
		// for (int i = 0; i < n; ++i)
		// {
		//     reverse(all(ops[i]));
		//     pii val = ops[i].back().f;
		//     res.updSeg(i, i + 1, -val.s - val.f);
		// }

		// for (auto [seg, vals] : updates)
		// {
		//     res.updSeg(seg.f, seg.s, vals.s);
		//     int p = res.getGoodPos();
		//     while (p < n)
		//     {
		//         ans[ops[p].back().s] = vals.f;
		//         ops[p].pop_back();
		//         pii val = ops[p].back().f;
		//         res.updSeg(p, p + 1, -val.s - val.f - res.getPos(p));
		//         p = res.getGoodPos();
		//     }
		// }

		for (auto el : ans)
			cout << el << '\n';
	}
};

main()
{
	boost();
	int q = 1;
	// cin >> q;
	for (int i = 0; i < q; i++)
	{
		test t;
		t.solve(i);
	}
	return 0;
}
//[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//
//                                                                                    //
//                               Coded by Der_Vlἀpos                                  //
//                                                                                    //
//[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//

Compilation message

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

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 7312 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 393 ms 29052 KB Output is correct
2 Correct 255 ms 29504 KB Output is correct
3 Correct 381 ms 33808 KB Output is correct
4 Correct 293 ms 32776 KB Output is correct
5 Correct 276 ms 30436 KB Output is correct
6 Correct 366 ms 34720 KB Output is correct
7 Correct 57 ms 10616 KB Output is correct
8 Correct 71 ms 11620 KB Output is correct
9 Correct 370 ms 36388 KB Output is correct
10 Correct 356 ms 36416 KB Output is correct
11 Correct 301 ms 33788 KB Output is correct
12 Correct 388 ms 34648 KB Output is correct
13 Correct 345 ms 34452 KB Output is correct
14 Correct 355 ms 33532 KB Output is correct
15 Correct 353 ms 34292 KB Output is correct
16 Correct 411 ms 34732 KB Output is correct
17 Correct 347 ms 34360 KB Output is correct
18 Correct 330 ms 33820 KB Output is correct
19 Correct 391 ms 33712 KB Output is correct
20 Correct 338 ms 34204 KB Output is correct
21 Correct 376 ms 34304 KB Output is correct
22 Correct 366 ms 33600 KB Output is correct
23 Correct 343 ms 33632 KB Output is correct
24 Correct 345 ms 34412 KB Output is correct
25 Correct 262 ms 33516 KB Output is correct
26 Correct 271 ms 33820 KB Output is correct
27 Correct 226 ms 36536 KB Output is correct

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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