oj.uz

Submission #442637

# Submission time Handle Problem Language Result Execution time Memory
442637 2021-07-08T11:41:48 Z prvocislo Cake (CEOI14_cake) C++17
100 / 100
 464 ms 14604 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1 << 18; int k = 10;
class intervalac
{
    vector<int> m;
public:
    intervalac(): m(vector<int>(maxn*2, -1)) {}
    void update(int i, int x)
    {
        m[i += maxn] = x;
        for (i = (i >> 1); i > 0; i >>= 1) m[i] = max(m[i<<1], m[i<<1|1]); 
    }
    int maxi(int l, int r)
    {
        int ans = 0;
        for (l += maxn, r += maxn+1; l < r; l >>= 1, r >>= 1)
        {
            if (l&1) ans = max(ans, m[l++]);
            if (r&1) ans = max(ans, m[--r]);
        }
        return ans;
    }
    int small(int x) // najde prvy kolac ktory je vacsi ako x
    {
        for (int i = 2; ; i <<= 1)
        {
            if (m[i] < x) i++;
            if (i >= maxn) return i - maxn;
        }
    }
};
vector<int> t(maxn);
bool cmp(int i, int j) { return t[i] > t[j]; }
intervalac in[2];
int n, q, a;
int ly(int i) { return i > a; } 
int id(int i) { return ly(i) == 0 ? a - 1 - i : i - a - 1; }
void upd(int i, int x) { if (i ^ a) in[ly(i)].update(id(i), x); }
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); 
    cin >> n >> a; a--; k = min(k, n);
    vector<int> best; // {chut, index}
    for (int i = 0; i < n; i++) cin >> t[i], best.push_back(i), upd(i, t[i]);
    sort(best.begin(), best.end(), cmp), best.resize(k);
    int num = n+1;
    upd(-1, 1e9), upd(n, 1e9);
    cin >> q;
    while (q--)
    {
        char c; cin >> c;
        if (c == 'E') // update
        {
            int i, e; cin >> i >> e; i--, e--;
            for (int j = 0; j < k; j++) if (best[j] == i) best.erase(best.begin()+j);
            best.insert(best.begin()+e, i); best.resize(k);
            for (int i = k-1; i >= 0; i--) t[best[i]] = num++, upd(best[i], t[best[i]]);
        }
        else // query
        {
            int b; cin >> b; b--;
            if (b == a)
            {
                cout << "0\n";
                continue;
            }
            int l = ly(b), i = id(b);
            int mx = in[l].maxi(0, i), cnt = in[l^1].small(mx);
            cout << cnt + abs(a - b) << "\n";
        }
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5452 KB Output is correct
2 Correct 3 ms 5452 KB Output is correct
3 Correct 3 ms 5440 KB Output is correct
4 Correct 6 ms 5452 KB Output is correct
5 Correct 12 ms 5708 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 10020 KB Output is correct
2 Correct 421 ms 9896 KB Output is correct
3 Correct 442 ms 10028 KB Output is correct
4 Correct 456 ms 9912 KB Output is correct
5 Correct 451 ms 10408 KB Output is correct
6 Correct 438 ms 10656 KB Output is correct
7 Correct 448 ms 10404 KB Output is correct
8 Correct 464 ms 10788 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 7876 KB Output is correct
2 Correct 66 ms 7796 KB Output is correct
3 Correct 61 ms 7648 KB Output is correct
4 Correct 4 ms 5452 KB Output is correct
5 Correct 127 ms 9552 KB Output is correct
6 Correct 128 ms 9608 KB Output is correct
7 Correct 105 ms 9432 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5920 KB Output is correct
2 Correct 35 ms 5908 KB Output is correct
3 Correct 70 ms 6996 KB Output is correct
4 Correct 66 ms 6812 KB Output is correct
5 Correct 95 ms 6840 KB Output is correct
6 Correct 117 ms 7876 KB Output is correct
7 Correct 128 ms 7628 KB Output is correct
8 Correct 220 ms 8416 KB Output is correct
9 Correct 439 ms 14484 KB Output is correct
10 Correct 312 ms 10192 KB Output is correct
11 Correct 330 ms 11316 KB Output is correct
12 Correct 431 ms 14092 KB Output is correct
13 Correct 415 ms 14604 KB Output is correct