oj.uz

Submission #490179

# Submission time Handle Problem Language Result Execution time Memory
490179 2021-11-26T05:46:11 Z SirCovidThe19th Cake (CEOI14_cake) C++17
0 / 100
 731 ms 6856 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 * (i - n + 10) : 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 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 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 239 ms 460 KB Output isn't correct
2 Correct 249 ms 588 KB Output is correct
3 Incorrect 250 ms 588 KB Output isn't correct
4 Correct 243 ms 588 KB Output is correct
5 Incorrect 265 ms 876 KB Output isn't correct
6 Incorrect 264 ms 844 KB Output isn't correct
7 Incorrect 262 ms 844 KB Output isn't correct
8 Correct 269 ms 844 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 2816 KB Output isn't correct
2 Incorrect 211 ms 2708 KB Output isn't correct
3 Incorrect 202 ms 2780 KB Output isn't correct
4 Incorrect 0 ms 332 KB Output isn't correct
5 Incorrect 307 ms 5900 KB Output isn't correct
6 Incorrect 271 ms 5912 KB Output isn't correct
7 Incorrect 279 ms 5700 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 468 KB Output isn't correct
2 Incorrect 55 ms 580 KB Output isn't correct
3 Incorrect 108 ms 1576 KB Output isn't correct
4 Incorrect 108 ms 1504 KB Output isn't correct
5 Incorrect 179 ms 668 KB Output isn't correct
6 Incorrect 191 ms 2000 KB Output isn't correct
7 Incorrect 223 ms 1028 KB Output isn't correct
8 Incorrect 147 ms 2468 KB Output isn't correct
9 Incorrect 675 ms 6856 KB Output isn't correct
10 Incorrect 536 ms 1580 KB Output isn't correct
11 Incorrect 601 ms 2120 KB Output isn't correct
12 Incorrect 669 ms 5880 KB Output isn't correct
13 Incorrect 731 ms 6792 KB Output isn't correct