Submission #1161455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161455		Der_Vlapos	Modern Machine (JOI23_ho_t5)	C++20	25 / 100	3085 ms	11600 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define pb push_back

const int BIG = 1e9 + 10;
#define int ll

struct segTreeSum
{
	vector<pii> tree;
	int sz;

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

	void upd(int v, int lv, int rv, int val)
	{
		tree[v].f = (rv - lv) * val;
		tree[v].s = val;
	}

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

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

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

	int get(int l, int r, int v, int lv, int rv)
	{
		push(v, lv, rv);
		if (l <= lv and rv <= r)
			return tree[v].f;
		if (r <= lv or rv <= l)
			return 0;
		int m = (lv + rv) >> 1;
		return get(l, r, v * 2 + 1, lv, m) + get(l, r, v * 2 + 2, m, rv);
	}

	int get(int l, int r)
	{
		return get(l, r, 0, 0, sz);
	}

	int getKthFromStart(int k, int v, int lv, int rv)
	{
		push(v, lv, rv);
		if (rv - lv == 1)
		{
			assert(k == 0);
			return lv;
		}
		int m = (lv + rv) >> 1;
		if (tree[v * 2 + 1].f <= k)
			return getKthFromStart(k - tree[v * 2 + 1].f, v * 2 + 2, m, rv);
		return getKthFromStart(k, v * 2 + 1, lv, m);
	}

	int getKthFromStart(int k)
	{
		return getKthFromStart(k, 0, 0, sz);
	}

	int getKthFromEnd(int k, int v, int lv, int rv)
	{
		push(v, lv, rv);
		if (rv - lv == 1)
		{
			assert(k == 0);
			return lv;
		}
		int m = (lv + rv) >> 1;
		if (tree[v * 2 + 2].f <= k)
		{
			return getKthFromEnd(k - tree[v * 2 + 2].f, v * 2 + 1, lv, m);
		}
		return getKthFromEnd(k, v * 2 + 2, m, rv);
	}

	int getKthFromEnd(int k)
	{
		return getKthFromEnd(k, 0, 0, sz);
	}
};

struct test
{
	void solve()
	{
		int n, m;
		cin >> n >> m;
		vector<int> a(n);
		vector<segTreeSum> tree(2);

		tree[0].init(n);
		tree[1].init(n);

		for (int i = 0; i < n; ++i)
		{
			char x;
			cin >> x;
			a[i] = x == 'R';
			tree[a[i]].set(i, i + 1, 1);
		}
		vector<int> P(m);
		for (int i = 0; i < m; ++i)
		{
			cin >> P[i];
			P[i]--;
		}

		bool good = true;
		{
			bool wasOne = false;
			for (int i = 0; i < n; ++i)
			{
				if (a[i])
					wasOne = true;
				else if (wasOne)
					good = false;
			}
		}

		int q;
		cin >> q;
		auto bf = a;
		for (int i = 0; i < q; ++i)
		{
			int l, r;
			cin >> l >> r;
			--l, --r;

			// if (!good)
			{
				for (int i = 0; i < n; ++i)
				{
					tree[a[i]].set(i, i + 1, 1);
					tree[1 - a[i]].set(i, i + 1, 0);
				}

				for (int i = l; i <= r; ++i)
				{
					int p = P[i];
					tree[1].set(p, p + 1, 1);
					tree[0].set(p, p + 1, 0);
					int c1 = tree[0].get(p, n);
					int c2 = tree[1].get(0, p + 1);
					if (c1 >= c2)
					{
						int leftMostPos = tree[0].getKthFromStart(tree[0].get(0, p + 1) + c2 - 1);
						tree[0].set(0, leftMostPos + 1, 0);
						tree[1].set(0, leftMostPos + 1, 1);
					}
					else
					{
						int rightMostPos = tree[1].getKthFromEnd(tree[1].get(p + 1, n) + c1);
						tree[0].set(rightMostPos, n, 1);
						tree[1].set(rightMostPos, n, 0);
					}
				}

				cout << tree[1].get(0, n) << "\n";
			}
			// else
			// {
			// 	int c1 = n;
			// 	for (int i = l; i <= r; ++i)
			// 	{
			// 		int p = P[i];
			// 		c1 = (p + (p >= c1) + c1 + 1) % (n + 1);
			// 	}
			// 	cout << c1 << "\n";
			// }
		}
	}
};

main()
{
	test t;
	t.solve();
}

Compilation message (stderr)

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

• Subtask 1: 3 / 3
• Subtask 2: 12 / 12
• Subtask 3: 10 / 10
• Subtask 4: 0 / 11
• Subtask 5: 0 / 26
• Subtask 6: 0 / 17
• Subtask 7: 0 / 21