oj.uz

답안 #678214

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
678214 2023-01-05T10:11:42 Z haxorman 케이크 (CEOI14_cake) C++14
30 / 100
 2000 ms 5676 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;

    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);
                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 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:100: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]
  100 |             for (int i = 0; i < nums.size(); ++i) {
      |                             ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 8 ms 444 KB Output is correct
5 Correct 65 ms 824 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 920 KB Output is correct
2 Correct 149 ms 940 KB Output is correct
3 Correct 157 ms 936 KB Output is correct
4 Correct 115 ms 944 KB Output is correct
5 Correct 197 ms 1232 KB Output is correct
6 Correct 245 ms 1196 KB Output is correct
7 Correct 178 ms 1112 KB Output is correct
8 Correct 125 ms 1244 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2056 ms 2708 KB Time limit exceeded
2 Execution timed out 2051 ms 3100 KB Time limit exceeded
3 Correct 444 ms 3136 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Execution timed out 2055 ms 5672 KB Time limit exceeded
6 Execution timed out 2081 ms 5660 KB Time limit exceeded
7 Execution timed out 2060 ms 5676 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 812 KB Output is correct
2 Correct 301 ms 900 KB Output is correct
3 Execution timed out 2045 ms 1832 KB Time limit exceeded
4 Execution timed out 2067 ms 1788 KB Time limit exceeded
5 Correct 260 ms 1004 KB Output is correct
6 Execution timed out 2029 ms 2468 KB Time limit exceeded
7 Correct 394 ms 1396 KB Output is correct
8 Correct 394 ms 2716 KB Output is correct
9 Execution timed out 2011 ms 5644 KB Time limit exceeded
10 Correct 912 ms 1768 KB Output is correct
11 Correct 1755 ms 2508 KB Output is correct
12 Execution timed out 2041 ms 4664 KB Time limit exceeded
13 Execution timed out 2091 ms 5672 KB Time limit exceeded