oj.uz

Submission #677634

# Submission time Handle Problem Language Result Execution time Memory
677634 2023-01-04T05:12:38 Z vjudge1 Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 16984 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;
            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 352 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 336 ms 5224 KB Output isn't correct
2 Correct 200 ms 5384 KB Output is correct
3 Correct 251 ms 5280 KB Output is correct
4 Correct 128 ms 5276 KB Output is correct
5 Incorrect 365 ms 6392 KB Output isn't correct
6 Incorrect 326 ms 6792 KB Output isn't correct
7 Correct 258 ms 6668 KB Output is correct
8 Correct 166 ms 6732 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2083 ms 7132 KB Time limit exceeded
2 Execution timed out 2033 ms 7852 KB Time limit exceeded
3 Correct 470 ms 8000 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Execution timed out 2062 ms 16964 KB Time limit exceeded
6 Execution timed out 2079 ms 16816 KB Time limit exceeded
7 Execution timed out 2088 ms 16972 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 1032 KB Output isn't correct
2 Correct 245 ms 1152 KB Output is correct
3 Execution timed out 2087 ms 4308 KB Time limit exceeded
4 Execution timed out 2093 ms 4544 KB Time limit exceeded
5 Incorrect 285 ms 1868 KB Output isn't correct
6 Correct 1886 ms 6388 KB Output is correct
7 Correct 331 ms 3016 KB Output is correct
8 Correct 420 ms 8644 KB Output is correct
9 Execution timed out 2095 ms 16972 KB Time limit exceeded
10 Incorrect 855 ms 5236 KB Output isn't correct
11 Incorrect 1651 ms 7216 KB Output isn't correct
12 Execution timed out 2075 ms 13780 KB Time limit exceeded
13 Execution timed out 2081 ms 16984 KB Time limit exceeded