oj.uz

Submission #678196

# Submission time Handle Problem Language Result Execution time Memory
678196 2023-01-05T09:44:14 Z haxorman Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 16976 KB 
#include <bits/stdc++.h>
using namespace std;
const int mxN = 3e5 + 7;
const int SZ = exp2(ceil(log2(mxN)));
int seg[2 * SZ];
void update(int pos, int val) {
    seg[pos += SZ - 1] = val;
    for (pos /= 2; pos; pos /= 2) {
        seg[pos] = max(seg[2 * pos], seg[2 * pos + 1]);
    }
}
int query(int a, int b, int ind = 1, int l = 1, int r = SZ) {
    if (l > b || r < a) {
        return 0;
    }
    if (a <= l && r <= b) {
        return seg[ind];
    }
    int mid = (l + r) / 2;
    return max(query(a, b, 2 * ind, l, mid),
               query(a, b, 2 * ind + 1, mid + 1, r));
}
int walk(int a, int b, int val, bool dir, int ind = 1, int l = 1, int r = SZ) {
    if (l > b || r < a || seg[ind] < val) {
        return 0;
    }
    int mid = (l + r) / 2;
    if (a <= l && r <= b) {
        if (l == r) {
            return l;
        }
        else if ((!dir && seg[2 * ind] > val) || (dir && seg[2 * ind + 1] < val)) {
            walk(a, b, val, dir, 2 * ind, l, mid);
        }
        else {
            walk(a, b, val, dir, 2 * ind + 1, mid + 1, r);
        }
    }
    int ret = 0;
    ret = (!dir ? walk(a, b, val, dir, 2 * ind, l, mid) :
                  walk(a, b, val, dir, 2 * ind + 1, mid + 1, r));
    if (!ret) {
        ret = (!dir ? walk(a, b, val, dir, 2 * ind + 1, mid + 1, r) :
                      walk(a, b, val, dir, 2 * ind, l, mid));
    }
    return ret;
}
int arr[mxN];
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, a;
    cin >> n >> a;
    set<pair<int,int>> nums;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
        nums.insert({-arr[i], i});
        update(i, arr[i]);
    }
    int q;
    cin >> q;
    while (q--) {
        char type;
        cin >> type;
        if (type == 'F') {
            int b;
            cin >> b;
            if (b == a) {
                cout << "0\n";
            }
            else if (b < a) {
                int mx = query(b, a - 1);
                int ind = walk(min(n, a + 1), n, mx, false);
                if (!ind) {
                    ind = n + 1;
                }
                cout << (ind - a) + (a - b - 1) << "\n";
            }
            else {
                int mx = query(a + 1, b);
                int ind = walk(1, max(1, a - 1), mx, true);
                cout << (a - ind - 1) + (b - a) << "\n";
            }
        }
        else {
            int i, e;
            cin >> i >> e;
            auto it = nums.begin();
            int ind = 1;
            vector<pair<int,int>> change;
            while (ind < e) {
                change.push_back(*it);
                ++it, ++ind;
            }
            for (auto x : change) {
                int cur = -x.first;
                update(x.second, cur + 1);
                nums.erase(x);
                nums.insert({x.first - 1, x.second});
            }
            int val = (-((*it).first)) + 1;
            if (nums.count({-arr[i], i})) {
                nums.erase({-arr[i], i});
            }
            nums.insert({-val, i});
            update(i, val);
            while (nums.size() > 10) {
                nums.erase(*nums.rbegin());
            }
        }
    }
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 328 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 352 ms 5224 KB Output isn't correct
2 Correct 223 ms 5272 KB Output is correct
3 Correct 289 ms 5372 KB Output is correct
4 Correct 151 ms 5272 KB Output is correct
5 Incorrect 414 ms 6384 KB Output isn't correct
6 Incorrect 326 ms 6796 KB Output isn't correct
7 Correct 269 ms 6664 KB Output is correct
8 Correct 145 ms 6792 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 7140 KB Time limit exceeded
2 Execution timed out 2072 ms 7936 KB Time limit exceeded
3 Correct 484 ms 7996 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Execution timed out 2065 ms 16964 KB Time limit exceeded
6 Execution timed out 2065 ms 16812 KB Time limit exceeded
7 Execution timed out 2077 ms 16976 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 988 KB Output isn't correct
2 Correct 273 ms 1164 KB Output is correct
3 Execution timed out 2086 ms 4296 KB Time limit exceeded
4 Execution timed out 2077 ms 4388 KB Time limit exceeded
5 Incorrect 274 ms 1852 KB Output isn't correct
6 Correct 1990 ms 6320 KB Output is correct
7 Correct 362 ms 3072 KB Output is correct
8 Correct 488 ms 8652 KB Output is correct
9 Execution timed out 2059 ms 16960 KB Time limit exceeded
10 Incorrect 919 ms 5256 KB Output isn't correct
11 Incorrect 1838 ms 7056 KB Output isn't correct
12 Execution timed out 2077 ms 13648 KB Time limit exceeded
13 Execution timed out 2072 ms 16944 KB Time limit exceeded