Submission #72550486

Source Code Expand

#include <stdio.h>
int n, q;
long long max(long long x, long long y) { return x > y ? x : y; }
namespace segmentTree1
{
	long long val[800005], lazy[800005];
	int lson(int x) { return x << 1; }
	int rson(int x) { return x << 1 | 1; }
	void pushdown(int root, int tl, int tr)
	{
		if (lazy[root])
			if (~lazy[root])
			{
				val[root] += lazy[root];
				if (tl != tr)
				{
					if (lazy[lson(root)] == -1)
						pushdown(lson(root), tl, (tl + tr) >> 1);
					lazy[lson(root)] += lazy[root];
					if (lazy[rson(root)] == -1)
						pushdown(rson(root), ((tl + tr) >> 1) + 1, tr);
					lazy[rson(root)] += lazy[root];
				}
			}
			else
			{
				val[root] = 0;
				if (tl != tr)
					lazy[lson(root)] = lazy[rson(root)] = -1;
			}
		lazy[root] = 0;
	}
	long long update(int l, int r, int x, int root, int tl, int tr)
	{
		pushdown(root, tl, tr);
		if (r < tl || tr < l)
			return val[root];
		if (l <= tl && tr <= r)
		{
			lazy[root] = x;
			pushdown(root, tl, tr);
			return val[root];
		}
		int tm = (tl + tr) >> 1;
		return val[root] = max(update(l, r, x, lson(root), tl, tm), update(l, r, x, rson(root), tm + 1, tr));
	}
	long long clear(int l, int r, int root, int tl, int tr)
	{
		pushdown(root, tl, tr);
		if (r < tl || tr < l)
			return val[root];
		if (l <= tl && tr <= r)
		{
			lazy[root] = -1;
			pushdown(root, tl, tr);
			return val[root];
		}
		int tm = (tl + tr) >> 1;
		return val[root] = max(clear(l, r, lson(root), tl, tm), clear(l, r, rson(root), tm + 1, tr));
	}
	long long query(int l, int r, int root, int tl, int tr)
	{
		if (r < tl || tr < l)
			return 0;
		pushdown(root, tl, tr);
		if (l <= tl && tr <= r)
			return val[root];
		int tm = (tl + tr) >> 1;
		return max(query(l, r, lson(root), tl, tm), query(l, r, rson(root), tm + 1, tr));
	}
}
namespace segmentTree2
{
	int val[800005];
	bool lazy[800005];
	int lson(int x) { return x << 1; }
	int rson(int x) { return x << 1 | 1; }
	void pushdown(int root, int tl, int tr)
	{
		if (lazy[root])
		{
			val[root] = tr - tl + 1 - val[root];
			if (tl != tr)
			{
				lazy[lson(root)] ^= 1;
				lazy[rson(root)] ^= 1;
			}
			lazy[root] = false;
		}
	}
	int update(int l, int r, int root, int tl, int tr)
	{
		pushdown(root, tl, tr);
		if (r < tl || tr < l)
			return val[root];
		if (l <= tl && tr <= r)
		{
			lazy[root] = true;
			pushdown(root, tl, tr);
			return val[root];
		}
		int tm = (tl + tr) >> 1;
		return val[root] = update(l, r, lson(root), tl, tm) + update(l, r, rson(root), tm + 1, tr);
	}
	int query(int l, int r, int root, int tl, int tr)
	{
		pushdown(root, tl, tr);
		if (r < tl || tr < l)
			return 0;
		if (l <= tl && tr <= r)
			return val[root];
		int tm = (tl + tr) >> 1;
		return query(l, r, lson(root), tl, tm) + query(l, r, rson(root), tm + 1, tr);
	}
}
int main()
{
	scanf("%d%d", &n, &q);
	while (~--q)
	{
		int opt;
		scanf("%d", &opt);
		if (opt == 1)
		{
			int l, r, x;
			scanf("%d%d%d", &l, &r, &x);
			int ll = l, rr = n + 1;
			while (ll < rr)
			{
				int mid = (ll + rr) >> 1;
				if (segmentTree2::query(l, mid, 1, 1, n) == mid - l + 1)
					ll = mid + 1;
				else
					rr = mid;
			}
			l = ll;
			ll = 0, rr = r;
			while (ll < rr)
			{
				int mid = (ll + rr + 1) >> 1;
				if (segmentTree2::query(mid, r, 1, 1, n) == r - mid + 1)
					rr = mid - 1;
				else
					ll = mid;
			}
			r = ll;
			if (l <= r)
				segmentTree1::update(l, r, x, 1, 1, n);
		}
		else if (opt == 2)
		{
			int l, r;
			scanf("%d%d", &l, &r);
			int ll = 1, rr = l;
			while (ll < rr)
			{
				int mid = (ll + rr) >> 1;
				if (segmentTree2::query(mid, l - 1, 1, 1, n) == l - mid)
					rr = mid;
				else
					ll = mid + 1;
			}
			int nl = ll;
			ll = r, rr = n;
			while (ll < rr)
			{
				int mid = (ll + rr + 1) >> 1;
				if (segmentTree2::query(r + 1, mid, 1, 1, n) == mid - r)
					ll = mid;
				else
					rr = mid - 1;
			}
			int nr = ll;
			segmentTree1::clear(nl, nr, 1, 1, n);
			segmentTree2::update(l, r, 1, 1, n);
		}
		else
		{
			int l, r;
			scanf("%d%d", &l, &r);
			int ll = l, rr = n + 1;
			while (ll < rr)
			{
				int mid = (ll + rr) >> 1;
				if (segmentTree2::query(l, mid, 1, 1, n) == mid - l + 1)
					ll = mid + 1;
				else
					rr = mid;
			}
			l = ll;
			ll = 0, rr = r;
			while (ll < rr)
			{
				int mid = (ll + rr + 1) >> 1;
				if (segmentTree2::query(mid, r, 1, 1, n) == r - mid + 1)
					rr = mid - 1;
				else
					ll = mid;
			}
			r = ll;
			printf("%lld\n", segmentTree1::query(l, r, 1, 1, n));
		}
	}
	return 0;
}

Submission Info

Submission Time
Task G - Takoyaki and Flip
User XiangXunyi
Language C++23 (GCC 15.2.0)
Score 575
Code Size 4651 Byte
Status AC
Exec Time 1546 ms
Memory 12436 KiB

Compile Error

./Main.cpp: In function 'void segmentTree1::pushdown(int, int, int)':
./Main.cpp:11:20: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   11 |                 if (lazy[root])
      |                    ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 575 / 575
Status
AC × 3
AC × 65
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 01_random_33.txt, 01_random_34.txt, 01_random_35.txt, 01_random_36.txt, 01_random_37.txt, 01_random_38.txt, 01_random_39.txt, 01_random_40.txt, 01_random_41.txt, 01_random_42.txt, 01_random_43.txt, 01_random_44.txt, 01_random_45.txt, 01_random_46.txt, 01_random_47.txt, 01_random_48.txt, 01_random_49.txt, 01_random_50.txt, 01_random_51.txt, 01_random_52.txt, 01_random_53.txt, 01_random_54.txt, 01_random_55.txt, 01_random_56.txt, 01_random_57.txt, 01_random_58.txt, 01_random_59.txt, 01_random_60.txt, 01_random_61.txt, 01_random_62.txt, 01_random_63.txt, 01_random_64.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 1644 KiB
00_sample_01.txt AC 1 ms 1616 KiB
00_sample_02.txt AC 0 ms 1604 KiB
01_random_03.txt AC 1529 ms 12412 KiB
01_random_04.txt AC 1527 ms 12368 KiB
01_random_05.txt AC 1532 ms 12396 KiB
01_random_06.txt AC 1541 ms 12404 KiB
01_random_07.txt AC 1530 ms 12368 KiB
01_random_08.txt AC 1540 ms 12352 KiB
01_random_09.txt AC 1546 ms 12368 KiB
01_random_10.txt AC 1536 ms 12436 KiB
01_random_11.txt AC 1534 ms 12288 KiB
01_random_12.txt AC 1520 ms 12420 KiB
01_random_13.txt AC 1527 ms 12436 KiB
01_random_14.txt AC 1530 ms 12368 KiB
01_random_15.txt AC 1541 ms 12284 KiB
01_random_16.txt AC 313 ms 4288 KiB
01_random_17.txt AC 897 ms 4136 KiB
01_random_18.txt AC 592 ms 6908 KiB
01_random_19.txt AC 804 ms 6908 KiB
01_random_20.txt AC 850 ms 7060 KiB
01_random_21.txt AC 991 ms 4372 KiB
01_random_22.txt AC 63 ms 12344 KiB
01_random_23.txt AC 97 ms 4340 KiB
01_random_24.txt AC 1407 ms 12428 KiB
01_random_25.txt AC 1444 ms 12412 KiB
01_random_26.txt AC 1445 ms 12352 KiB
01_random_27.txt AC 1427 ms 12284 KiB
01_random_28.txt AC 1437 ms 12288 KiB
01_random_29.txt AC 1442 ms 12284 KiB
01_random_30.txt AC 1432 ms 12368 KiB
01_random_31.txt AC 1413 ms 12344 KiB
01_random_32.txt AC 388 ms 7036 KiB
01_random_33.txt AC 749 ms 12196 KiB
01_random_34.txt AC 743 ms 3080 KiB
01_random_35.txt AC 478 ms 6988 KiB
01_random_36.txt AC 787 ms 12364 KiB
01_random_37.txt AC 1369 ms 5372 KiB
01_random_38.txt AC 1379 ms 5328 KiB
01_random_39.txt AC 1376 ms 5244 KiB
01_random_40.txt AC 1375 ms 5160 KiB
01_random_41.txt AC 1379 ms 5156 KiB
01_random_42.txt AC 1386 ms 5356 KiB
01_random_43.txt AC 1377 ms 5364 KiB
01_random_44.txt AC 1378 ms 5156 KiB
01_random_45.txt AC 539 ms 5160 KiB
01_random_46.txt AC 416 ms 3452 KiB
01_random_47.txt AC 630 ms 5328 KiB
01_random_48.txt AC 914 ms 2256 KiB
01_random_49.txt AC 354 ms 3512 KiB
01_random_50.txt AC 293 ms 2196 KiB
01_random_51.txt AC 291 ms 2180 KiB
01_random_52.txt AC 289 ms 2124 KiB
01_random_53.txt AC 1444 ms 12412 KiB
01_random_54.txt AC 1430 ms 12352 KiB
01_random_55.txt AC 1431 ms 12368 KiB
01_random_56.txt AC 1439 ms 12352 KiB
01_random_57.txt AC 1432 ms 12368 KiB
01_random_58.txt AC 648 ms 6976 KiB
01_random_59.txt AC 628 ms 12420 KiB
01_random_60.txt AC 551 ms 12368 KiB
01_random_61.txt AC 1251 ms 9936 KiB
01_random_62.txt AC 1254 ms 9860 KiB
01_random_63.txt AC 1255 ms 9636 KiB
01_random_64.txt AC 30 ms 1672 KiB