oj.uz

Submission #490276

# Submission time Handle Problem Language Result Execution time Memory
490276 2021-11-26T17:31:45 Z SirCovidThe19th Cake (CEOI14_cake) C++17
0 / 100
 675 ms 7032 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) ? i : mQ * (i - n + 10);
    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 233 ms 852 KB Output isn't correct
2 Correct 250 ms 728 KB Output is correct
3 Incorrect 238 ms 716 KB Output isn't correct
4 Correct 238 ms 968 KB Output is correct
5 Incorrect 248 ms 1012 KB Output isn't correct
6 Incorrect 268 ms 844 KB Output isn't correct
7 Incorrect 250 ms 900 KB Output isn't correct
8 Correct 258 ms 844 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 210 ms 2980 KB Output isn't correct
2 Incorrect 200 ms 2696 KB Output isn't correct
3 Incorrect 195 ms 2648 KB Output isn't correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Incorrect 275 ms 5872 KB Output isn't correct
6 Incorrect 278 ms 5808 KB Output isn't correct
7 Incorrect 269 ms 5676 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 460 KB Output isn't correct
2 Incorrect 56 ms 508 KB Output isn't correct
3 Incorrect 100 ms 1532 KB Output isn't correct
4 Incorrect 101 ms 1572 KB Output isn't correct
5 Incorrect 158 ms 708 KB Output isn't correct
6 Incorrect 191 ms 2072 KB Output isn't correct
7 Incorrect 214 ms 1156 KB Output isn't correct
8 Incorrect 137 ms 2344 KB Output isn't correct
9 Incorrect 675 ms 6812 KB Output isn't correct
10 Incorrect 520 ms 1504 KB Output isn't correct
11 Incorrect 541 ms 2228 KB Output isn't correct
12 Incorrect 660 ms 5816 KB Output isn't correct
13 Incorrect 657 ms 7032 KB Output isn't correct