oj.uz

Submission #676578

# Submission time Handle Problem Language Result Execution time Memory
676578 2022-12-31T10:47:24 Z vjudge1 Cake (CEOI14_cake) C++17
0 / 100
 2000 ms 24608 KB 
#include <bits/stdc++.h>
using namespace std;

#define double long double

const int mxN = 3e5 + 7;
const int SZ = exp2(ceil(log2(mxN)));

double seg[2 * SZ];

void update(int pos, double val) {
    seg[pos += SZ - 1] = val;
    
    for (pos /= 2; pos; pos /= 2) {
        seg[pos] = max(seg[2 * pos], seg[2 * pos + 1]);
    }
}

double 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, double 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;
}

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

        update(i, x);
        nums.insert(-x);
    }

    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;
            
            nums.erase(-query(i, i));
            if (e == 1) {
                update(i, -(*nums.begin() - 1));
                nums.insert(*nums.begin() - 1);
            }
            else {
                int ind = 2;
                auto it = nums.begin();
                while (ind < e) {
                    ++it, ++ind;
                }
                
                int val = ((*it++) + (*it)) / 2;
                update(i, -val);
                nums.insert(val);
            }
        }
    }
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 336 ms 1572 KB Output isn't correct
2 Incorrect 316 ms 1656 KB Output isn't correct
3 Incorrect 315 ms 1560 KB Output isn't correct
4 Correct 360 ms 1748 KB Output is correct
5 Incorrect 364 ms 2936 KB Output isn't correct
6 Incorrect 361 ms 2984 KB Output isn't correct
7 Incorrect 352 ms 2976 KB Output isn't correct
8 Correct 370 ms 3020 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 9756 KB Time limit exceeded
2 Execution timed out 2077 ms 10088 KB Time limit exceeded
3 Incorrect 1576 ms 10188 KB Output isn't correct
4 Correct 0 ms 340 KB Output is correct
5 Execution timed out 2089 ms 23912 KB Time limit exceeded
6 Execution timed out 2074 ms 23932 KB Time limit exceeded
7 Execution timed out 2085 ms 23792 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 160 ms 716 KB Output isn't correct
2 Incorrect 43 ms 920 KB Output isn't correct
3 Incorrect 114 ms 5320 KB Output isn't correct
4 Execution timed out 2072 ms 5264 KB Time limit exceeded
5 Incorrect 394 ms 840 KB Output isn't correct
6 Incorrect 189 ms 6976 KB Output isn't correct
7 Incorrect 147 ms 1892 KB Output isn't correct
8 Incorrect 238 ms 9932 KB Output isn't correct
9 Execution timed out 2079 ms 23940 KB Time limit exceeded
10 Incorrect 1276 ms 1664 KB Output isn't correct
11 Incorrect 620 ms 3696 KB Output isn't correct
12 Incorrect 1148 ms 20800 KB Output isn't correct
13 Execution timed out 2099 ms 24608 KB Time limit exceeded