| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 873757 |
2023-11-15T16:20:58 Z |
thuanqvbn03 |
Cake (CEOI14_cake) |
C++17 |
|
994 ms |
38828 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;
Node(int label = 0) {
parent = children[0] = children[1] = NULL;
this->label = label;
treeSize = 1;
}
int getDir(Node *a) { return (a == children[0] ? 0 : 1); }
void pushUp() {
treeSize = 1;
for (int i = 0; i < 2; i++) {
treeSize += (children[i] == NULL ? 0 : children[i]->treeSize);
}
}
};
int treeSize(Node *p) { return (p == NULL ? 0 : p->treeSize); }
struct SplayTree {
Node *root;
SplayTree(Node *node = NULL) {
root = node;
if (root != NULL) {
root->parent = NULL;
}
}
void link(Node *a, Node *b, int dir) {
if (a == NULL) {
root = b;
if (root != NULL) {
root->parent = NULL;
}
return;
}
a->children[dir] = b;
if (b != NULL) {
b->parent = a;
}
}
void rotate(Node *a, int dir) {
Node *b = a->children[dir];
Node *p = a->parent;
int parDir = (p == NULL ? 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 != NULL) {
int dir = a->parent->getDir(a);
if (a->parent->parent == NULL) {
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];
}
}
}
int getPos(Node *p) {
splay(p);
return treeSize(root->children[0]) + 1;
}
void merge(SplayTree other) {
if (other.root == NULL) {
return;
}
if (root == NULL) {
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 = NULL;
return SplayTree(tmp);
}
find(pos - 1);
Node *tmp = root->children[1];
root->children[1] = NULL;
tmp->parent = NULL;
root->pushUp();
return SplayTree(tmp);
}
Node *insert(int label) {
Node *tmp = new Node(label);
merge(SplayTree(tmp));
return tmp;
}
void moveTree(int from, int to) {
SplayTree tmp = split(from + 1);
SplayTree subtree = split(from);
merge(tmp);
tmp = split(to - 1);
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;
};
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];
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(NULL);
for (auto &[u, v] : tmp) {
nodes[v] = splayTree.insert(v);
}
}
void buildCurrentRate() {
for (int i = 1; i <= numQuery; i++) {
if (queries[i].type == 'E') {
queries[i].u = splayTree.getPos(nodes[queries[i].pos]);
queries[i].v = numCake - queries[i].v + 1;
splayTree.moveTree(queries[i].u, queries[i].v);
}
}
}
void buildTarget() {
ft.init(numCake + numQuery);
for (int i = 1; i <= numCake; i++) {
ft.update(i, 1);
}
int maxValue = numCake;
for (int i = 1; i <= numQuery; i++) {
if (queries[i].type == 'E') {
maxValue++;
queries[i].u = ft.lifting(queries[i].u);
ft.update(queries[i].u, -1);
ft.update(maxValue, 1);
}
}
for (int i = numQuery; i >= 1; i--) {
if (queries[i].type == 'E') {
queries[i].v = ft.lifting(queries[i].v);
ft.update(queries[i].u, 1);
ft.update(queries[i].v, -1);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
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();
buildCurrentRate();
buildTarget();
for (int i = 1; i <= numCake; i++)
{
cake[i] = ft.lifting(cake[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);
} 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 |
4440 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
323 ms |
17764 KB |
Output isn't correct |
| 2 |
Correct |
197 ms |
17856 KB |
Output is correct |
| 3 |
Correct |
282 ms |
17900 KB |
Output is correct |
| 4 |
Correct |
187 ms |
17784 KB |
Output is correct |
| 5 |
Incorrect |
368 ms |
21100 KB |
Output isn't correct |
| 6 |
Correct |
305 ms |
21384 KB |
Output is correct |
| 7 |
Correct |
299 ms |
21248 KB |
Output is correct |
| 8 |
Correct |
202 ms |
21484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
256 ms |
17600 KB |
Output is correct |
| 2 |
Correct |
154 ms |
17460 KB |
Output is correct |
| 3 |
Incorrect |
167 ms |
17484 KB |
Output isn't correct |
| 4 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 5 |
Correct |
291 ms |
28636 KB |
Output is correct |
| 6 |
Incorrect |
329 ms |
28164 KB |
Output isn't correct |
| 7 |
Incorrect |
270 ms |
28012 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
7448 KB |
Output isn't correct |
| 2 |
Correct |
58 ms |
7768 KB |
Output is correct |
| 3 |
Correct |
139 ms |
13516 KB |
Output is correct |
| 4 |
Correct |
116 ms |
13756 KB |
Output is correct |
| 5 |
Incorrect |
123 ms |
8688 KB |
Output isn't correct |
| 6 |
Correct |
265 ms |
15944 KB |
Output is correct |
| 7 |
Correct |
197 ms |
12368 KB |
Output is correct |
| 8 |
Correct |
166 ms |
20528 KB |
Output is correct |
| 9 |
Incorrect |
994 ms |
38828 KB |
Output isn't correct |
| 10 |
Incorrect |
406 ms |
17572 KB |
Output isn't correct |
| 11 |
Correct |
546 ms |
20128 KB |
Output is correct |
| 12 |
Correct |
921 ms |
35364 KB |
Output is correct |
| 13 |
Incorrect |
930 ms |
38792 KB |
Output isn't correct |
