oj.uz

Submission #676589

# Submission time Handle Problem Language Result Execution time Memory
676589 2022-12-31T11:14:13 Z vjudge1 Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 16536 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], pos[mxN];

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
    int n, a;
    cin >> n >> a;
    
    set<int> nums;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
        pos[arr[i]] = i;

        nums.insert(-arr[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;
            
            pos[arr[i]] = 0;
            nums.erase(-arr[i]);

            auto it = nums.begin();
            int ind = 1;
            while (ind < e) {
                ++it, ++ind;
            }

            int val = *it - 1;

            
            it = nums.begin();
            vector<int> change;
            for (int j = 1; j < ind; ++j) {
                change.push_back(*it);
                ++it;
            }

            for (auto x : change) {
                int cur = -x;
                
                update(pos[cur], cur + 1);
                pos[cur + 1] = pos[cur];
                pos[cur] = 0;
                
                nums.erase(x);
                nums.insert(x - 1);
            }
            nums.insert(val);
            arr[i] = -val;
            pos[arr[i]] = i;
            update(i, arr[i]);
        }
    }
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 340 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 549 ms 9856 KB Output isn't correct
2 Correct 249 ms 3280 KB Output is correct
3 Incorrect 352 ms 7928 KB Output isn't correct
4 Correct 140 ms 3008 KB Output is correct
5 Incorrect 566 ms 10624 KB Output isn't correct
6 Incorrect 484 ms 10212 KB Output isn't correct
7 Incorrect 382 ms 8644 KB Output isn't correct
8 Correct 192 ms 3832 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 6972 KB Time limit exceeded
2 Execution timed out 2045 ms 7124 KB Time limit exceeded
3 Correct 417 ms 7184 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Execution timed out 2060 ms 16380 KB Time limit exceeded
6 Execution timed out 2059 ms 16264 KB Time limit exceeded
7 Execution timed out 2072 ms 16176 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 1188 KB Output isn't correct
2 Correct 246 ms 1132 KB Output is correct
3 Execution timed out 2076 ms 3940 KB Time limit exceeded
4 Execution timed out 2074 ms 4180 KB Time limit exceeded
5 Incorrect 319 ms 2416 KB Output isn't correct
6 Correct 1741 ms 5484 KB Output is correct
7 Correct 382 ms 2848 KB Output is correct
8 Correct 473 ms 8608 KB Output is correct
9 Execution timed out 2075 ms 16336 KB Time limit exceeded
10 Incorrect 1006 ms 6860 KB Output isn't correct
11 Incorrect 1759 ms 7772 KB Output isn't correct
12 Execution timed out 2068 ms 13408 KB Time limit exceeded
13 Execution timed out 2074 ms 16536 KB Time limit exceeded