oj.uz

답안 #1000868

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1000868 2024-06-18T10:36:19 Z aykhn 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 284 ms 118880 KB 
#include <bits/stdc++.h>

using namespace std;

#define inf 0x3F3F3F3F

struct Node
{
	int val = 0, l = -1, r = -1;
};

const int MXN = 1e5 + 5;
const int mod = 1e9 + 7;
const int LOG = 31;

int m, c = 1;
vector<Node> st(2, {0, -1, -1});
vector<int> lz(2, -1);

void relax(int l, int r, int x)
{
	if (lz[x] == -1) return;
	st[x].val = (r - l + 1);
	if (l == r) 
	{
		lz[x] = -1;
		return;
	}
	if (st[x].l == -1)
	{
		lz.push_back(-1);
		st.push_back({0, -1, -1});
	}
	if (st[x].r == -1)
	{
		lz.push_back(-1);
		st.push_back({0, -1, -1});
	}
	lz[(st[x].l == -1 ? st[x].l = ++c : st[x].l)] = lz[(st[x].r == -1 ? st[x].r = ++c : st[x].r)] = lz[x];
	lz[x] = -1;
}
void make(int l, int r, int x, int lx, int rx)
{
	relax(l, r, x);
	if (l > rx || r < lx) return;
	if (l >= lx && r <= rx)
	{
		lz[x] = 1;
		relax(l, r, x);
		return;
	}
	int mid = (l + r) >> 1;
	if (st[x].l == -1)
	{
		lz.push_back(-1);
		st.push_back({0, -1, -1});
	}
	if (st[x].r == -1)
	{
		lz.push_back(-1);
		st.push_back({0, -1, -1});
	}
	make(l, mid, (st[x].l == -1 ? st[x].l = ++c : st[x].l), lx, rx);
	make(mid + 1, r, (st[x].r == -1 ? st[x].r = ++c : st[x].r), lx, rx);
	st[x].val = (st[x].l != -1 ? st[st[x].l].val : 0) + (st[x].r != -1 ? st[st[x].r].val : 0);
}
int get(int l, int r, int x, int lx, int rx)
{
	if (l > rx || r < lx) return 0;
	relax(l, r, x);
	if (l >= lx && r <= rx) return st[x].val; 
	int mid = (l + r) >> 1;
	return (st[x].l != -1 ? get(l, mid, st[x].l, lx, rx) : 0) + (st[x].r != -1 ? get(mid + 1, r, st[x].r, lx, rx) : 0);
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> m;
	int p = 0;
	while (m--)
	{
		int t;
		cin >> t;
		if (t == 1)
		{
			int l, r;
			cin >> l >> r;
			l += p, r += p;
			cout << (p = get(1, 1e9, 1, l, r)) << '\n';
		}
		else
		{
			int l, r;
			cin >> l >> r;
			l += p, r += p;
			make(1, 1e9, 1, l, r);
		}
	}
}

Compilation message

apple.cpp: In function 'void relax(int, int, int)':
apple.cpp:39:32: warning: operation on 'c' may be undefined [-Wsequence-point]
   39 |  lz[(st[x].l == -1 ? st[x].l = ++c : st[x].l)] = lz[(st[x].r == -1 ? st[x].r = ++c : st[x].r)] = lz[x];
      |                                ^~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 10 ms 4836 KB Output is correct
5 Correct 12 ms 5092 KB Output is correct
6 Correct 12 ms 4320 KB Output is correct
7 Correct 13 ms 4324 KB Output is correct
8 Correct 74 ms 32116 KB Output is correct
9 Correct 167 ms 61844 KB Output is correct
10 Correct 173 ms 59800 KB Output is correct
11 Correct 177 ms 61084 KB Output is correct
12 Correct 175 ms 59552 KB Output is correct
13 Correct 161 ms 63368 KB Output is correct
14 Correct 160 ms 64220 KB Output is correct
15 Correct 262 ms 117388 KB Output is correct
16 Correct 263 ms 117900 KB Output is correct
17 Correct 170 ms 66436 KB Output is correct
18 Correct 167 ms 66184 KB Output is correct
19 Correct 277 ms 118880 KB Output is correct
20 Correct 284 ms 118000 KB Output is correct