QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #472449 | #6409. Classical Data Structure Problem | UESTC_DECAYALI# | RE | 0ms | 3764kb | C++17 | 5.8kb | 2024-07-11 16:32:17 | 2024-07-11 16:32:17 |
Judging History
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).lc == 0 && $(nd).rc == 0);
assert($(nd).tree_l == $(nd).l && $(nd).tree_r == $(nd).r);
assert($(nd).siz == 1);
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 -= $($(rk).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) {
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
80 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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
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: 3696kb
input:
1 1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3460kb
input:
1 2 3 1
output:
3
result:
ok 1 number(s): "3"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
1 5 31 15
output:
17
result:
ok 1 number(s): "17"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
1 20 366738 218765
output:
147974
result:
ok 1 number(s): "147974"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
1 30 86669484 41969116
output:
44700369
result:
ok 1 number(s): "44700369"
Test #7:
score: -100
Runtime Error
input:
10 5 20 31 2 2 14 18 13 25 26 4 22 9 15 9 19 16 15 27 9 20