oj.uz

Submission #677635

# Submission time Handle Problem Language Result Execution time Memory
677635 2023-01-04T05:13:20 Z haxorman Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 15184 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 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 340 ms 880 KB Output isn't correct
2 Correct 208 ms 944 KB Output is correct
3 Correct 228 ms 940 KB Output is correct
4 Correct 131 ms 936 KB Output is correct
5 Incorrect 347 ms 1792 KB Output isn't correct
6 Incorrect 328 ms 1816 KB Output isn't correct
7 Correct 258 ms 1820 KB Output is correct
8 Correct 129 ms 1812 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 6276 KB Time limit exceeded
2 Execution timed out 2082 ms 6560 KB Time limit exceeded
3 Correct 428 ms 6664 KB Output is correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Execution timed out 2087 ms 15052 KB Time limit exceeded
6 Execution timed out 2087 ms 15116 KB Time limit exceeded
7 Execution timed out 2094 ms 15088 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 636 KB Output isn't correct
2 Correct 258 ms 716 KB Output is correct
3 Execution timed out 2086 ms 3544 KB Time limit exceeded
4 Execution timed out 2077 ms 3564 KB Time limit exceeded
5 Incorrect 252 ms 796 KB Output isn't correct
6 Correct 1737 ms 4584 KB Output is correct
7 Correct 340 ms 1400 KB Output is correct
8 Correct 415 ms 6220 KB Output is correct
9 Execution timed out 2079 ms 15112 KB Time limit exceeded
10 Incorrect 862 ms 1520 KB Output isn't correct
11 Incorrect 1582 ms 2788 KB Output isn't correct
12 Execution timed out 2098 ms 12124 KB Time limit exceeded
13 Execution timed out 2081 ms 15184 KB Time limit exceeded