| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 874455 |
2023-11-17T04:44:42 Z |
thuanqvbn03 |
Cake (CEOI14_cake) |
C++17 |
|
1172 ms |
60032 KB |
// Flower_On_Stone
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 500005;
struct Node {
Node *parent, *children[2];
int label;
int treeSize;
int weight;
int sumWeight;
Node(int label = 0) {
parent = children[0] = children[1] = nullptr;
this->label = label;
treeSize = 1;
weight = 1;
sumWeight = 1;
}
int getDir(Node *a) { return (a == children[0] ? 0 : 1); }
void pushUp() {
treeSize = 1;
sumWeight = weight;
for (int i = 0; i < 2; i++) {
treeSize += (children[i] == nullptr ? 0 : children[i]->treeSize);
sumWeight += (children[i] == nullptr ? 0 : children[i]->sumWeight);
}
}
};
int treeSize(Node *p) { return (p == nullptr ? 0 : p->treeSize); }
int sumWeight(Node *p) { return (p == nullptr ? 0 : p->sumWeight); }
struct SplayTree {
Node *root;
SplayTree(Node *node = nullptr) {
root = node;
if (root != nullptr) {
root->parent = nullptr;
}
}
void link(Node *a, Node *b, int dir) {
if (a == nullptr) {
root = b;
if (root != nullptr) {
root->parent = nullptr;
}
return;
}
a->children[dir] = b;
if (b != nullptr) {
b->parent = a;
}
}
void rotate(Node *a, int dir) {
Node *b = a->children[dir];
Node *p = a->parent;
int parDir = (p == nullptr ? 0 : p->getDir(a));
link(a, b->children[dir ^ 1], dir);
link(b, a, dir ^ 1);
link(p, b, parDir);
}
void splay(Node *a) {
while (a->parent != nullptr) {
int dir = a->parent->getDir(a);
if (a->parent->parent == nullptr) {
rotate(a->parent, dir);
a->children[dir ^ 1]->pushUp();
} else {
int parDir = a->parent->parent->getDir(a->parent);
if (parDir == dir) {
rotate(a->parent->parent, parDir);
rotate(a->parent, dir);
a->children[dir ^ 1]->children[parDir ^ 1]->pushUp();
a->children[dir ^ 1]->pushUp();
} else {
rotate(a->parent, dir);
rotate(a->parent, parDir);
for (int i = 0; i < 2; i++) {
a->children[i]->pushUp();
}
}
}
a->pushUp();
}
}
void find(int pos) {
Node *p = root;
while (true) {
int left = treeSize(p->children[0]);
int mid = 1;
if (left >= pos) {
p = p->children[0];
} else if (left + mid >= pos) {
return splay(p);
} else {
pos -= left + mid;
p = p->children[1];
}
}
}
void findWeight(int pos) {
Node *p = root;
while (true) {
int left = sumWeight(p->children[0]);
int mid = (p->weight);
if (left >= pos) {
p = p->children[0];
} else if (left + mid >= pos) {
return splay(p);
} else {
pos -= left + mid;
p = p->children[1];
}
}
}
int getPos(Node *p) {
splay(p);
return treeSize(root->children[0]) + 1;
}
int getWeight(Node *p) {
splay(p);
return sumWeight(root->children[0]) + p->weight;
}
void merge(SplayTree other) {
if (other.root == nullptr) {
return;
}
if (root == nullptr) {
root = other.root;
return;
}
find(treeSize(root));
link(root, other.root, 1);
root->pushUp();
}
SplayTree split(int pos) {
if (pos > treeSize(root)) {
return SplayTree();
}
if (pos == 1) {
Node *tmp = root;
root = nullptr;
return SplayTree(tmp);
}
find(pos - 1);
Node *tmp = root->children[1];
root->children[1] = nullptr;
tmp->parent = nullptr;
root->pushUp();
return SplayTree(tmp);
}
Node *insert(int label) {
Node *tmp = new Node(label);
merge(SplayTree(tmp));
return tmp;
}
void insert(SplayTree tree, int pos) {
findWeight(pos - 1);
SplayTree tmp = split(getPos(root) + 1);
merge(tree);
merge(tmp);
}
void moveTree(int from, int to) {
SplayTree tmp = split(from + 1);
SplayTree subtree = split(from);
merge(tmp);
tmp = split(to);
merge(subtree);
merge(tmp);
}
int query(int pos) {
find(pos);
return root->label;
}
};
struct SegmentTree {
private:
int treeSize;
vector<int> nodes, leaf;
void initTree(int id, int low, int high, int arr[]) {
if (low == high) {
nodes[id] = arr[low];
leaf[low] = id;
return;
}
int mid = (low + high) / 2;
initTree(id * 2, low, mid, arr);
initTree(id * 2 + 1, mid + 1, high, arr);
nodes[id] = max(nodes[id * 2], nodes[id * 2 + 1]);
}
int get(int id, int low, int high, int left, int right) {
if (low > right || high < left) {
return 0;
}
if (low >= left && high <= right) {
return nodes[id];
}
int mid = (low + high) / 2;
return max(get(id * 2, low, mid, left, right),
get(id * 2 + 1, mid + 1, high, left, right));
}
public:
void init(int treeSize, int arr[]) {
this->treeSize = treeSize;
int tmp = 1;
while (tmp < treeSize) {
tmp *= 2;
}
nodes.resize(tmp * 2);
leaf.resize(treeSize + 1);
initTree(1, 1, treeSize, arr);
}
void update(int id, int value) {
id = leaf[id];
nodes[id] = value;
while (id > 1) {
id /= 2;
nodes[id] = max(nodes[id * 2], nodes[id * 2 + 1]);
}
}
int get(int left, int right) { return get(1, 1, treeSize, left, right); }
} smt;
struct Query {
char type;
int pos, u, v;
Node *uNode, *vNode;
};
struct FenwickTree {
int treeSize, logTreeSize;
vector<int> nodes;
void init(int treeSize) {
this->treeSize = treeSize;
nodes.assign(treeSize + 1, 0);
logTreeSize = log2(treeSize) + 1;
}
void update(int id, int val) {
for (; id <= treeSize; id += (id & -id)) {
nodes[id] += val;
}
}
int get(int id) {
int result = 0;
for (; id >= 1; id -= (id & -id)) {
result += nodes[id];
}
return result;
}
int lifting(int value) {
int sum = 0, pos = 0;
for (int i = logTreeSize; i >= 0; i--) {
if (pos + (1 << i) <= treeSize &&
sum + nodes[pos + (1 << i)] < value) {
pos += (1 << i);
sum += nodes[pos];
}
}
return pos + 1;
}
} ft;
int numCake, firstEat, numQuery, maxCake;
int cake[MAX_N];
SplayTree splayTree;
Query queries[MAX_N];
Node *nodes[MAX_N], *initNode[MAX_N];
void buildSplayTree() {
vector<pair<int, int>> tmp(numCake);
for (int i = 1; i <= numCake; i++) {
tmp[i - 1] = make_pair(cake[i], i);
}
sort(tmp.begin(), tmp.end());
splayTree = SplayTree(nullptr);
for (auto &[u, v] : tmp) {
nodes[v] = initNode[v] = splayTree.insert(v);
}
}
void buildQuery() {
for (int i = 1; i <= numQuery; i++) {
if (queries[i].type == 'E') {
queries[i].uNode = nodes[queries[i].pos];
splayTree.getWeight(queries[i].uNode);
splayTree.root->weight = 0;
splayTree.root->pushUp();
queries[i].v = numCake - queries[i].v + 1;
SplayTree tmp = SplayTree();
nodes[queries[i].pos] = queries[i].vNode =
tmp.insert(queries[i].pos);
splayTree.insert(tmp, queries[i].v);
}
}
for (int i = 1; i <= numQuery; i++) {
if (queries[i].type == 'E') {
queries[i].u = splayTree.getPos(queries[i].uNode);
queries[i].v = splayTree.getPos(queries[i].vNode);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifdef Flower_On_Stone
freopen("input.txt", "r", stdin);
freopen("test.txt", "w", stdout);
#endif
cin >> numCake >> firstEat;
maxCake = numCake;
for (int i = 1; i <= numCake; i++) {
cin >> cake[i];
}
cin >> numQuery;
for (int i = 1; i <= numQuery; i++) {
cin >> queries[i].type;
if (queries[i].type == 'E') {
cin >> queries[i].pos >> queries[i].v;
} else {
cin >> queries[i].pos;
}
}
buildSplayTree();
buildQuery();
for (int i = 1; i <= numCake; i++) {
cake[i] = splayTree.getPos(initNode[i]);
}
smt.init(numCake, cake);
for (int i = 1; i <= numQuery; i++) {
if (queries[i].type == 'E') {
smt.update(queries[i].pos, queries[i].v);
cake[queries[i].pos] = queries[i].v;
} else {
if (queries[i].pos == firstEat) {
cout << 0 << '\n';
continue;
} else if (queries[i].pos < firstEat) {
int maxSegment = smt.get(queries[i].pos, firstEat - 1);
int low = firstEat, high = numCake;
while (low <= high) {
int mid = (low + high) / 2;
if (smt.get(firstEat + 1, mid) < maxSegment) {
low = mid + 1;
} else {
high = mid - 1;
}
}
cout << high - queries[i].pos << '\n';
} else {
int maxSegment = smt.get(firstEat + 1, queries[i].pos);
int low = 1, high = firstEat;
while (low <= high) {
int mid = (low + high) / 2;
if (smt.get(mid, firstEat - 1) < maxSegment) {
high = mid - 1;
} else {
low = mid + 1;
}
}
cout << queries[i].pos - low << '\n';
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
6 ms |
6748 KB |
Output is correct |
| 5 |
Correct |
16 ms |
7512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
397 ms |
49356 KB |
Output is correct |
| 2 |
Correct |
193 ms |
49488 KB |
Output is correct |
| 3 |
Correct |
300 ms |
49356 KB |
Output is correct |
| 4 |
Correct |
171 ms |
49488 KB |
Output is correct |
| 5 |
Correct |
416 ms |
52864 KB |
Output is correct |
| 6 |
Correct |
329 ms |
53072 KB |
Output is correct |
| 7 |
Correct |
324 ms |
52980 KB |
Output is correct |
| 8 |
Correct |
178 ms |
53232 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
272 ms |
22836 KB |
Output is correct |
| 2 |
Correct |
147 ms |
22836 KB |
Output is correct |
| 3 |
Correct |
166 ms |
22716 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
373 ms |
32644 KB |
Output is correct |
| 6 |
Correct |
422 ms |
32724 KB |
Output is correct |
| 7 |
Correct |
264 ms |
32632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
10328 KB |
Output is correct |
| 2 |
Correct |
60 ms |
10520 KB |
Output is correct |
| 3 |
Correct |
150 ms |
18704 KB |
Output is correct |
| 4 |
Correct |
119 ms |
18804 KB |
Output is correct |
| 5 |
Correct |
136 ms |
17756 KB |
Output is correct |
| 6 |
Correct |
289 ms |
26980 KB |
Output is correct |
| 7 |
Correct |
212 ms |
20052 KB |
Output is correct |
| 8 |
Correct |
223 ms |
34812 KB |
Output is correct |
| 9 |
Correct |
1172 ms |
59900 KB |
Output is correct |
| 10 |
Correct |
455 ms |
37564 KB |
Output is correct |
| 11 |
Correct |
610 ms |
39592 KB |
Output is correct |
| 12 |
Correct |
1073 ms |
56704 KB |
Output is correct |
| 13 |
Correct |
999 ms |
60032 KB |
Output is correct |
