oj.uz

Submission #676591

# Submission time Handle Problem Language Result Execution time Memory
676591 2022-12-31T11:30:47 Z vjudge1 Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 25236 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);
        }
    }
}

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 584 ms 23812 KB Output isn't correct
2 Correct 293 ms 24024 KB Output is correct
3 Correct 391 ms 23944 KB Output is correct
4 Correct 207 ms 24400 KB Output is correct
5 Incorrect 627 ms 24096 KB Output isn't correct
6 Incorrect 515 ms 24212 KB Output isn't correct
7 Correct 409 ms 24236 KB Output is correct
8 Correct 226 ms 25236 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2082 ms 6380 KB Time limit exceeded
2 Execution timed out 2068 ms 6712 KB Time limit exceeded
3 Correct 426 ms 6656 KB Output is correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Execution timed out 2085 ms 15136 KB Time limit exceeded
6 Execution timed out 2085 ms 15044 KB Time limit exceeded
7 Execution timed out 2033 ms 15072 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 115 ms 1652 KB Output isn't correct
2 Correct 250 ms 1688 KB Output is correct
3 Execution timed out 2070 ms 3620 KB Time limit exceeded
4 Execution timed out 2080 ms 4008 KB Time limit exceeded
5 Incorrect 302 ms 4196 KB Output isn't correct
6 Correct 1819 ms 6092 KB Output is correct
7 Correct 369 ms 5580 KB Output is correct
8 Correct 481 ms 13644 KB Output is correct
9 Execution timed out 2072 ms 15088 KB Time limit exceeded
10 Incorrect 1041 ms 13312 KB Output isn't correct
11 Incorrect 1786 ms 13576 KB Output isn't correct
12 Execution timed out 2088 ms 12252 KB Time limit exceeded
13 Execution timed out 2068 ms 15512 KB Time limit exceeded