#include <bits/stdc++.h>
int ri() {
int n;
scanf("%d", &n);
return n;
}
struct LCT {
#define l ch[0]
#define r ch[1]
struct Node {
Node *p;
Node *ch[2];
int val;
int sum;
int size;
void fetch() {
size = 1 + l->size + r->size;
sum = val + l->sum + r->sum;
}
void rotate(bool dir) {
Node *new_root = ch[!dir], *parent = p;
ch[!dir] = new_root->ch[dir];
ch[!dir]->p = this;
new_root->ch[dir] = this;
p = new_root;
fetch(), new_root->fetch();
new_root->p = parent;
if (parent->l == this) parent->l = new_root;
else if (parent->r == this) parent->r = new_root;
}
bool is_root() {
return p == LCT::NONE || (p->l != this && p->r != this);
}
};
void splay(Node *node) {
while (!node->is_root()) {
Node *p = node->p;
if (p->is_root()) {
p->rotate(p->l == node);
} else {
Node *pp = p->p;
bool flag1 = pp->l == p, flag2 = p->l == node;
if (flag1 == flag2) pp->rotate(flag1);
p->rotate(flag2);
if (flag1 != flag2) pp->rotate(flag1);
}
}
}
Node *expose(Node *start) {
Node *prev = NONE;
for (Node *cur = start; cur != NONE; cur = cur->p) {
splay(cur);
cur->r = prev;
cur->fetch();
prev = cur;
}
splay(start);
return prev;
}
void link(Node *child, Node *parent) {
// std::cerr << "link " << (child - nodes - 1) << "->" << (parent - nodes - 1) << std::endl;
assert(get_root(child) != get_root(parent));
expose(child);
expose(parent);
child->p = parent;
parent->r = child;
parent->fetch();
}
void cut(Node *child) {
// std::cerr << "cut " << (child - nodes - 1) << std::endl;
expose(child);
Node *parent = child->l;
parent->p = NONE;
child->l = NONE;
child->fetch();
}
Node *get_root(Node *node) {
expose(node);
for (; node->l != NONE; node = node->l);
return node;
}
static Node *nodes, *NONE;
static int head;
LCT () {
if (!head) nodes[head++] = {NONE, {NONE, NONE}, 0, 0, 0};
}
Node *new_node(int val) {
return &(nodes[head++] = {NONE, {NONE, NONE}, val, val, 1});
}
#undef l
#undef r
};
LCT::Node *LCT::nodes = (Node *) malloc(sizeof(Node) * 1000000), *LCT::NONE = nodes;
int LCT::head = 0;
struct Comp {
bool operator () (std::pair<int, int> a, std::pair<int, int> b) {
if (a.first != b.first) return a.first < b.first;
if ((a.second & 1) != (b.second & 1)) return (a.second & 1) < (b.second & 1);
return a.second < b.second;
}
};
int n, l;
std::vector<int> a;
LCT tree;
std::vector<LCT::Node *> nodes;
std::set<std::pair<int, int>, Comp> nodes_set;
template<class T>
void erase(T itr) {
if ((std::prev(itr)->second & 1) == 0) {
tree.cut(nodes[std::prev(itr)->second]);
tree.link(nodes[std::prev(itr)->second], nodes[std::next(itr)->second]);
}
}
template<class T>
void insert(T itr) {
if ((std::prev(itr)->second & 1) == 0) {
tree.cut(nodes[std::prev(itr)->second]);
tree.link(nodes[std::prev(itr)->second], nodes[itr->second]);
}
}
int update(int i, int pos) {
// erase
auto r0 = nodes_set.find({a[i], i * 2 + 1});
auto r1 = nodes_set.find({a[i] + l, i * 2 + 2});
assert(r0 != nodes_set.end());
assert(r1 != nodes_set.end());
erase(r0);
nodes_set.erase(r0);
erase(r1);
nodes_set.erase(r1);
a[i] = pos;
r0 = nodes_set.insert({a[i], i * 2 + 1}).first;
r1 = nodes_set.insert({a[i] + l, i * 2 + 2}).first;
tree.cut(nodes[r1->second]);
tree.link(nodes[r1->second], nodes[std::next(r1)->second]);
insert(r0);
insert(r1);
tree.expose(nodes[0]);
return nodes[0]->sum;
}
void init(int n_, int l_, int x[]) {
n = n_;
l = l_;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = x[i];
nodes_set.insert({-2000000000, nodes.size()});
nodes.push_back(tree.new_node(0));
for (int i = 0; i < n; i++) {
auto r0 = nodes_set.insert({a[i], nodes.size()}).first;
nodes.push_back(tree.new_node(1));
insert(r0);
auto r1 = nodes_set.insert({a[i] + l, nodes.size()}).first;
nodes.push_back(tree.new_node(0));
insert(r1);
tree.link(nodes[r0->second], nodes[r1->second]);
}
auto tmp = nodes_set.insert({2000000000, nodes.size()}).first;
nodes.push_back(tree.new_node(0));
insert(tmp);
}
/*
int main() {
int n = ri(), l = ri();
int a[n];
for (auto &i : a) i = ri();
assert(std::is_sorted(a, a + n));
init(n, l + 1, a);
int q = ri();
for (int i = 0; i < q; i++) {
int index = ri(), pos = ri();
int r0 = update(index, pos);
a[index] = pos;
int b[n];
memcpy(b, a, sizeof(a));
std::sort(b, b + n);
int r1 = 0;
for (int i = 0; i < n; ) {
int max = b[i] + l;
for (; i < n && b[i] <= max; i++);
r1++;
}
if (r0 != r1) {
std::cerr << "FAILED correct:" << r1 << " wrong:" << r0 << std::endl;
}
}
return 0;
}
//*/
Compilation message
elephants.cpp: In function 'int ri()':
elephants.cpp:5:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
376 KB |
Output is correct |
| 2 |
Correct |
6 ms |
380 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
376 KB |
Output is correct |
| 2 |
Correct |
6 ms |
380 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
376 KB |
Output is correct |
| 2 |
Correct |
6 ms |
380 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
376 KB |
Output is correct |
| 2 |
Correct |
6 ms |
380 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
376 KB |
Output is correct |
| 2 |
Correct |
6 ms |
380 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
