oj.uz

Submission #490177

# Submission time Handle Problem Language Result Execution time Memory
490177 2021-11-26T05:42:00 Z SirCovidThe19th Cake (CEOI14_cake) C++17
0 / 100
 759 ms 13220 KB 
#include <bits/stdc++.h>
using namespace std;

template<int sz> struct DS{
    int seg[sz * 2];
    void upd(int i, int v){
        seg[i += sz] = v;
        for (i /= 2; i; i /= 2) seg[i] = max(seg[i * 2], seg[i * 2 + 1]); 
    }
    int qry(int l, int r){ 
        int ans = 0;
        for (l += sz, r += sz; l <= r; r /= 2, l /= 2){
            if (l % 2 == 1) ans = max(ans, seg[l++]);
            if (r % 2 == 0) ans = max(seg[r--], ans);
        }
        return ans;
    }
    int walk(int v){
        int i = 1; 
        while (i < sz) i = (seg[i * 2] < v) ? i * 2 + 1 : i * 2;
        return i - sz - 1;
    }
}; 

const int mN = 2.5e5 + 5, mQ = 5e5 + 5;

int n, a, q, rnk[mN]; pair<int, int> tmp[mN]; DS<(1 << 19)> L, R;

int main(){
    cin >> n >> a;  

    for (int i = 1; i <= n; i++) cin >> tmp[i].first, tmp[i].second = i;
    sort(tmp + 1, tmp + n + 1);

    for (int i = 1; i <= n; i++) rnk[i] = ((i == n - 9) ? mQ * (n - i + 1) : i);
    for (int i = 1; i <= n; i++){
        int pos = tmp[i].second;
        if (pos < a) L.upd(a - pos, rnk[i]);
        if (pos > a) R.upd(pos - a, rnk[i]);
    }

    cin >> q; L.upd(a, 1e9); R.upd(n - a + 1, 1e9);
    while (q--){
        int pos; char type; cin >> type >> pos;
        if (type == 'E'){
            int e; cin >> e;
            if (pos < a) L.upd(a - pos, ++rnk[n - e + 1]);
            if (pos > a) R.upd(pos - a, ++rnk[n - e + 1]);
        }
        else{
            int ans = pos;
            if (pos < a) ans = R.walk(L.qry(1, a - pos)) + a;
            if (pos > a) ans = a - L.walk(R.qry(1, pos - a));
            cout<<abs(pos - ans)<<"\n";
        }
    }
}

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 271 ms 4912 KB Output isn't correct
2 Incorrect 243 ms 4928 KB Output isn't correct
3 Incorrect 249 ms 4920 KB Output isn't correct
4 Incorrect 260 ms 4940 KB Output isn't correct
5 Incorrect 251 ms 5468 KB Output isn't correct
6 Incorrect 260 ms 5872 KB Output isn't correct
7 Incorrect 257 ms 5864 KB Output isn't correct
8 Incorrect 278 ms 5864 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 226 ms 4252 KB Output isn't correct
2 Incorrect 207 ms 4132 KB Output isn't correct
3 Incorrect 201 ms 3872 KB Output isn't correct
4 Incorrect 1 ms 336 KB Output isn't correct
5 Incorrect 279 ms 8308 KB Output isn't correct
6 Incorrect 278 ms 8264 KB Output isn't correct
7 Incorrect 253 ms 7952 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 884 KB Output isn't correct
2 Incorrect 74 ms 968 KB Output isn't correct
3 Incorrect 102 ms 2400 KB Output isn't correct
4 Incorrect 101 ms 2388 KB Output isn't correct
5 Incorrect 163 ms 1836 KB Output isn't correct
6 Incorrect 198 ms 3820 KB Output isn't correct
7 Incorrect 221 ms 2580 KB Output isn't correct
8 Incorrect 149 ms 4772 KB Output isn't correct
9 Incorrect 698 ms 13192 KB Output isn't correct
10 Incorrect 523 ms 5192 KB Output isn't correct
11 Incorrect 558 ms 6404 KB Output isn't correct
12 Incorrect 672 ms 11792 KB Output isn't correct
13 Incorrect 759 ms 13220 KB Output isn't correct