oj.uz

Submission #678221

# Submission time Handle Problem Language Result Execution time Memory
678221 2023-01-05T10:16:47 Z haxorman Cake (CEOI14_cake) C++14
46.6667 / 100
 2000 ms 7712 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], vis[mxN], dp[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, vis_cnt = 1;
    cin >> q;
    while (q--) {
        char type;
        cin >> type;
        if (type == 'F') {
            int b;
            cin >> b;

            if (vis[b] == vis_cnt) {
                cout << dp[b] << "\n";
                continue;
            }

            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 << (dp[b] = (ind - a) + (a - b - 1)) << "\n";
            }
            else {
                int mx = query(a + 1, b);
                int ind = walk(1, max(1, a - 1), mx, true);
                cout << (dp[b] = (a - ind - 1) + (b - a)) << "\n";
            }
            vis[b] = vis_cnt;
        }
        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();
            }
            ++vis_cnt;
        }
    }
}

Compilation message

cake.cpp: In function 'int32_t main()':
cake.cpp:109: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]
  109 |             for (int i = 0; i < nums.size(); ++i) {
      |                             ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 65 ms 724 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 740 KB Output is correct
2 Correct 121 ms 700 KB Output is correct
3 Correct 153 ms 844 KB Output is correct
4 Correct 95 ms 772 KB Output is correct
5 Correct 172 ms 1132 KB Output is correct
6 Correct 153 ms 1108 KB Output is correct
7 Correct 162 ms 1168 KB Output is correct
8 Correct 103 ms 1148 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2094 ms 3380 KB Time limit exceeded
2 Correct 1170 ms 3704 KB Output is correct
3 Correct 80 ms 3648 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Execution timed out 2069 ms 7392 KB Time limit exceeded
6 Execution timed out 2097 ms 7580 KB Time limit exceeded
7 Correct 242 ms 7712 KB Output is correct

Subtask #4
16.666667 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 544 KB Output is correct
2 Correct 237 ms 768 KB Output is correct
3 Execution timed out 2096 ms 2108 KB Time limit exceeded
4 Execution timed out 2050 ms 2092 KB Time limit exceeded
5 Correct 220 ms 772 KB Output is correct
6 Correct 1644 ms 2860 KB Output is correct
7 Correct 308 ms 1464 KB Output is correct
8 Correct 338 ms 3248 KB Output is correct
9 Execution timed out 2083 ms 7408 KB Time limit exceeded
10 Correct 697 ms 1512 KB Output is correct
11 Correct 1459 ms 2356 KB Output is correct
12 Execution timed out 2085 ms 6020 KB Time limit exceeded
13 Execution timed out 2086 ms 7508 KB Time limit exceeded