oj.uz

Submission #872880

# Submission time Handle Problem Language Result Execution time Memory
872880 2023-11-14T03:19:15 Z thuanqvbn03 Cake (CEOI14_cake) C++17
100 / 100
 731 ms 12464 KB 
// Flower_On_Stone
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 250005;

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;

int numCake, firstEat, numQuery, maxCake;
int cake[MAX_N];
int pos[15];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef Flower_On_Stone
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cin >> numCake >> firstEat;
    maxCake = numCake;
    for (int i = 1; i <= numCake; i++) {
        cin >> cake[i];
    }
    smt.init(numCake, cake);
    for (int i = 1; i <= numCake; i++) {
        for (int j = 1; j <= 10; j++) {
            if (cake[i] > cake[pos[j]]) {
                for (int k = 10; k > j; k--) {
                    pos[k] = pos[k - 1];
                }
                pos[j] = i;
                break;
            }
        }
    }
    cin >> numQuery;
    while (numQuery--) {
        char type;
        cin >> type;
        if (type == 'E') {
            int p, e;
            cin >> p >> e;
            if (pos[e] == p) {
                continue;
            }
            int current = 10;
            for (int i = 10; i >= e; i--) {
                if (pos[i] == p) {
                    current = i;
                    break;
                }
            }
            for (int i = current; i > e; i--) {
                pos[i] = pos[i - 1];
            }
            pos[e] = p;
            for (int i = e; i > 1; i--) {
                cake[pos[i]] = cake[pos[i - 1]];
                smt.update(pos[i], cake[pos[i]]);
            }
            maxCake++;
            cake[pos[1]] = maxCake;
            smt.update(pos[1], maxCake);
        } else {
            int x;
            cin >> x;
            if (x == firstEat) {
                cout << 0 << '\n';
                continue;
            } else if (x < firstEat) {
                int maxSegment = smt.get(x, 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 - x << '\n';
            } else {
                int maxSegment = smt.get(firstEat + 1, x);
                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 << x - low << '\n';
            }
        }
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 8 ms 592 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 4944 KB Output is correct
2 Correct 87 ms 4944 KB Output is correct
3 Correct 93 ms 5008 KB Output is correct
4 Correct 72 ms 4876 KB Output is correct
5 Correct 135 ms 5508 KB Output is correct
6 Correct 108 ms 5888 KB Output is correct
7 Correct 103 ms 5624 KB Output is correct
8 Correct 76 ms 5768 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 4176 KB Output is correct
2 Correct 158 ms 3924 KB Output is correct
3 Correct 137 ms 3924 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 220 ms 7400 KB Output is correct
6 Correct 254 ms 7456 KB Output is correct
7 Correct 222 ms 7188 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 924 KB Output is correct
2 Correct 40 ms 856 KB Output is correct
3 Correct 90 ms 2480 KB Output is correct
4 Correct 75 ms 2500 KB Output is correct
5 Correct 78 ms 1744 KB Output is correct
6 Correct 178 ms 3868 KB Output is correct
7 Correct 119 ms 2640 KB Output is correct
8 Correct 52 ms 4716 KB Output is correct
9 Correct 618 ms 12316 KB Output is correct
10 Correct 255 ms 5200 KB Output is correct
11 Correct 363 ms 6484 KB Output is correct
12 Correct 591 ms 11512 KB Output is correct
13 Correct 731 ms 12464 KB Output is correct