oj.uz

Submission #677636

# Submission time Handle Problem Language Result Execution time Memory
677636 2023-01-04T05:17:25 Z haxorman Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 15164 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 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 324 ms 888 KB Output isn't correct
2 Correct 200 ms 944 KB Output is correct
3 Correct 228 ms 936 KB Output is correct
4 Correct 124 ms 852 KB Output is correct
5 Incorrect 333 ms 1796 KB Output isn't correct
6 Incorrect 290 ms 1816 KB Output isn't correct
7 Correct 237 ms 1816 KB Output is correct
8 Correct 128 ms 1748 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2075 ms 6368 KB Time limit exceeded
2 Execution timed out 2091 ms 6552 KB Time limit exceeded
3 Correct 413 ms 6604 KB Output is correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Execution timed out 2100 ms 14964 KB Time limit exceeded
6 Execution timed out 2100 ms 15044 KB Time limit exceeded
7 Execution timed out 2096 ms 15164 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 564 KB Output isn't correct
2 Correct 232 ms 772 KB Output is correct
3 Execution timed out 2074 ms 3436 KB Time limit exceeded
4 Execution timed out 2062 ms 3532 KB Time limit exceeded
5 Incorrect 250 ms 752 KB Output isn't correct
6 Correct 1692 ms 4732 KB Output is correct
7 Correct 322 ms 1380 KB Output is correct
8 Correct 415 ms 6328 KB Output is correct
9 Execution timed out 2085 ms 15064 KB Time limit exceeded
10 Incorrect 838 ms 1496 KB Output isn't correct
11 Incorrect 1540 ms 2892 KB Output isn't correct
12 Execution timed out 2090 ms 12244 KB Time limit exceeded
13 Execution timed out 2048 ms 15052 KB Time limit exceeded