QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#472470#6409. Classical Data Structure ProblemUESTC_DECAYALI#WA 1ms3748kbC++175.8kb2024-07-11 16:39:062024-07-11 16:39:08

Judging History

你现在查看的是最新测评结果

  • [2024-07-11 16:39:08]
  • 评测
  • 测评结果：WA
  • 用时：1ms
  • 内存：3748kb
查看
  • [2024-07-11 16:39:06]
  • 提交

answer

#include <bits/stdc++.h>

constexpr int $n = 500000;

namespace Treap {
	void debug(int);
	
	std::mt19937 rng(/*(std::random_device())()*/114515);
	
	struct TreapNode {
		int lc, rc;
		int l, r;
		int tree_l, tree_r;
		uint32_t val, sum, tag;
		uint32_t w, siz;
	} node[$n * 2 + 5];
	
	inline TreapNode& $(size_t i) { return node[i]; }
	int O = 1;
	
	int newnode(int l, int r) {
		int res = O++;
		$(res).lc = $(res).rc = 0;
		$(res).l = $(res).tree_l = l;
		$(res).r = $(res).tree_r = r;
		$(res).val = $(res).sum = $(res).tag = 0;
		$(res).w = rng();
		$(res).siz = 1;
		return res;
	}
	
	void pushup(int i) {
		$(i).sum = $(i).val * uint32_t($(i).r - $(i).l + 1) + $($(i).lc).sum + $($(i).rc).sum;
		$(i).siz = 1 + $($(i).lc).siz + $($(i).rc).siz;
		if($(i).lc) $(i).tree_l = $($(i).lc).tree_l; else $(i).tree_l = $(i).l;
		if($(i).rc) $(i).tree_r = $($(i).rc).tree_r; else $(i).tree_r = $(i).r;
		
		return ;
	}
	
	void pushdown(int i) {
		if($(i).tag) {
			if($(i).lc) {
				TreapNode &lc = $($(i).lc);
				lc.val += $(i).tag;
				lc.tag += $(i).tag;
				lc.sum += $(i).tag * (lc.tree_l - lc.tree_r + 1);	
			}
			if($(i).rc) {
				TreapNode &rc = $($(i).rc);
				rc.val += $(i).tag;
				rc.tag += $(i).tag;
				rc.sum += $(i).tag * (rc.tree_l - rc.tree_r + 1);
			} 
			$(i).tag = 0;
		}
	}
	
	int merge(int l, int r) {
		if(!l) return r; if(!r) return l;
		pushdown(l), pushdown(r);
		if($(l).w > $(r).w) {
			$(l).rc = merge($(l).rc, r);
			pushup(l); return l;
		} else {
			$(r).lc = merge(l, $(r).lc);
			pushup(r); return r;
		}
	}
	
	int merge(int l, int m, int r) {
		return merge(merge(l, m), r);
	}
	
	std::pair<int, int> split_range(int nd, int d) {
		if(!nd) return {0, 0};
		if(d >= $(nd).r) return {nd, 0};
		if(d <  $(nd).l) return {0, nd};
		assert($(nd).l <= d && $(nd).r > d);
		assert($(nd).siz == 1);
		assert($(nd).lc == 0 && $(nd).rc == 0);
		assert($(nd).tree_l == $(nd).l && $(nd).tree_r == $(nd).r);
		int nn = newnode(d + 1, $(nd).r);
		$(nn).val = $(nd).val;
		pushup(nn);
		$(nd).r = d;
		pushup(nd);
		return {nd, nn};
	}
	
	std::pair<int, int> split_by(int nd, std::function<bool(int)> is_left) {
		// std::cerr << "nd = " << nd << char(10);
		if(!nd) return {0, 0};
		pushdown(nd);
		if(is_left(nd)) {
			auto [m, r] = split_by($(nd).rc, is_left);
			$(nd).rc = m; pushup(nd);
			return {nd, r};
		} else {
			auto [l, m] = split_by($(nd).lc, is_left);
			$(nd).lc = m; pushup(nd);
			return {l, nd};
		}
	}
	
	std::pair<int, int> split_by_rank(int nd, int rk) {
		return split_by(nd, [&rk] (int nd) {
			if($($(nd).lc).siz + 1 <= rk) {
				rk -= $($(nd).lc).siz + 1;
				return true;
			} else return false;
		});
	}
	
	std::tuple<int, int, int> fetch_range(int nd, int lb, int rb) {
//		std::cerr << "lb, rb = " << lb << ", " << rb << char(10);
		auto [L, MR] = split_by(nd, [lb] (int nd) {
			return $(nd).r < lb;
		});
		auto [M, R] = split_by(MR, [rb] (int nd) {
			return $(nd).l <= rb;
		});
		
//		debug(L);
//		debug(M);
//		debug(R);
		
		auto [lm, t1] = split_by_rank(M, 1);
		auto [l, t2] = split_range(lm, lb - 1);
//		std::cerr << "[debug] l = " << l << char(10);
		int M2 = merge(t2, t1);
		auto [t3, mr] = split_by_rank(M2, $(M2).siz - 1);
		auto [t4, r] = split_range(mr, rb);
		int M3 = merge(t3, t4);
		
		return {merge(L, l), M3, merge(r, R)};
	}
	
	void debug(int nd) {
		std::cerr << "[debug] ";
		if(nd == 0) std::cerr << "nd = null\n";
		else {
			std::cerr << "nd = " << nd << ":\n";
			std::cerr << "    l = " << $(nd).l << "\n";
			std::cerr << "    r = " << $(nd).r << "\n";
			std::cerr << "    tree_l = " << $(nd).tree_l << "\n";
			std::cerr << "    tree_r = " << $(nd).tree_r << "\n";
		}
		std::cerr << "----------\n";
	}
}

int n, m, p, q;
uint32_t x = 0;

int main(void) {
//	freopen("C2.in", "r", stdin);
	using Treap::$;
	std::cin >> n >> m;
	int root = Treap::newnode(0, (1 << m) - 1);
	for(uint32_t i = 1; i <= n; ++i) {
		std::cin >> p >> q;
		p = p + x & (1 << m) - 1;
		q = q + x & (1 << m) - 1;
		int l = p, r = q;
		if(l > r) std::swap(l, r);		
		auto [L, M, R] = Treap::fetch_range(root, l, r);
//		Treap::debug(L);
//		Treap::debug(M);
//		Treap::debug(R);
//		assert($(M).tree_l == l);
//		assert($(M).tree_r == r);
		$(M).val += i;
		$(M).tag += i;
		$(M).sum += i * uint32_t($(M).tree_r - $(M).tree_l + 1);
		x += $(M).sum;
//		std::cerr << "x = " << x << char(10);
		root = Treap::merge(L, M, R);
	}
	std::cout << (x & (1 << 30) - 1) << char(10);
	return 0;
}

/*
5 2
2 1
1 3
3 2
1 0
0 2

160 30
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810

114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810

114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810

114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810

114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810

114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810

114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810

114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810

114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810

114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
114514 1919810
*/
源文件, 语言: C++17

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3696kb

input:

5 2
2 1
1 3
3 2
1 0
0 2

output:

87

result:

ok 1 number(s): "87"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

1 1
1 1

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

1 2
3 1

output:

3

result:

ok 1 number(s): "3"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

1 5
31 15

output:

17

result:

ok 1 number(s): "17"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

1 20
366738 218765

output:

147974

result:

ok 1 number(s): "147974"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3492kb

input:

1 30
86669484 41969116

output:

44700369

result:

ok 1 number(s): "44700369"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3460kb

input:

10 5
20 31
2 2
14 18
13 25
26 4
22 9
15 9
19 16
15 27
9 20

output:

1414

result:

ok 1 number(s): "1414"

Test #8:

score: -100
Wrong Answer
time: 1ms
memory: 3748kb

input:

100 10
245 987
817 813
743 560
548 504
116 479
223 199
775 998
126 542
791 823
96 318
69 349
0 584
245 601
119 513
93 820
115 307
838 978
249 767
433 287
240 8
22 683
169 720
395 592
903 866
919 652
510 563
858 345
938 250
550 239
981 7
784 926
212 644
272 365
490 871
470 987
571 53
65 593
515 370
1...

output:

16395629

result:

wrong answer 1st numbers differ - expected: '20383734', found: '16395629'
English 繁體中文 简体中文

伺服器時間: 2024-11-30 18:54:44 | 開源專案