oj.uz

Submission #678234

# Submission time Handle Problem Language Result Execution time Memory
678234 2023-01-05T10:27:07 Z haxorman Cake (CEOI14_cake) C++14
0 / 100
 440 ms 9012 KB 
#include <bits/stdc++.h>
using namespace std;
const int mxN = 3e5 + 7;
const int SZ = exp2(ceil(log2(mxN)));
pair<int,int> seg[2 * SZ];

pair<int,int> cmb(pair<int,int> a, pair<int,int> b) {
    if (a.first > b.first || (a.first == b.first && a.second < b.second)) {
        return a;
    }
    return b;
}

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

pair<int,int> query(int a, int b, int ind = 1, int l = 1, int r = SZ) {
    if (l > b || r < a) {
        return {0, INT_MAX};
    }
    if (a <= l && r <= b) {
        return seg[ind];
    }
    int mid = (l + r) / 2;
    return cmb(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].first < val) {
        return 0;
    }

    int mid = (l + r) / 2;
    if (a <= l && r <= b) {
        return seg[ind].second;
    }

    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;

    vector<pair<int,int>> nums;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
        nums.push_back({arr[i], i});
        update(i, arr[i]);
    }
    sort(nums.begin(), nums.end(), greater<pair<int,int>>());

    while (nums.size() > 10) {
        nums.pop_back();
    }

    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).first;
                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).first;
                int ind = walk(1, max(1, a - 1), mx, true);
                cout << (a - ind - 1) + (b - a) << "\n";
            }
        }
        else {
            int ind, e;
            cin >> ind >> e;
            
            auto it = find(nums.begin(), nums.end(), make_pair(arr[ind], ind));
            if (it != nums.end()) {
                nums.erase(it);
            }

            for (int i = 0; i < nums.size(); ++i) {
                if (i == e - 1) {
                    int val = nums[i].first + 1;
                    update(ind, val);
                    arr[ind] = val;

                    nums.insert(nums.begin() + i, {val, ind});
                    break;
                }
                else {
                    nums[i].first += 2;
                    update(nums[i].second, nums[i].first);
                    arr[nums[i].second] = nums[i].first;
                }
            }

            while (nums.size() > 10) {
                nums.pop_back();
            }
        }
    }
}

Compilation message

cake.cpp: In function 'int32_t main()':
cake.cpp:105:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             for (int i = 0; i < nums.size(); ++i) {
      |                             ~~^~~~~~~~~~~~~

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 190 ms 744 KB Output isn't correct
2 Correct 142 ms 724 KB Output is correct
3 Incorrect 139 ms 772 KB Output isn't correct
4 Correct 93 ms 768 KB Output is correct
5 Incorrect 196 ms 1112 KB Output isn't correct
6 Incorrect 181 ms 1112 KB Output isn't correct
7 Incorrect 140 ms 1112 KB Output isn't correct
8 Correct 102 ms 1200 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 3780 KB Output isn't correct
2 Incorrect 72 ms 3700 KB Output isn't correct
3 Incorrect 62 ms 3624 KB Output isn't correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Incorrect 109 ms 7992 KB Output isn't correct
6 Incorrect 121 ms 7988 KB Output isn't correct
7 Correct 85 ms 7696 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 596 KB Output isn't correct
2 Incorrect 22 ms 604 KB Output isn't correct
3 Incorrect 44 ms 2004 KB Output isn't correct
4 Incorrect 56 ms 1992 KB Output isn't correct
5 Incorrect 88 ms 708 KB Output isn't correct
6 Incorrect 87 ms 2784 KB Output isn't correct
7 Incorrect 85 ms 1172 KB Output isn't correct
8 Incorrect 80 ms 3252 KB Output isn't correct
9 Incorrect 440 ms 9004 KB Output isn't correct
10 Incorrect 270 ms 1484 KB Output isn't correct
11 Incorrect 348 ms 2424 KB Output isn't correct
12 Incorrect 371 ms 7660 KB Output isn't correct
13 Incorrect 304 ms 9012 KB Output isn't correct