oj.uz

Submission #490178

# Submission time Handle Problem Language Result Execution time Memory
490178 2021-11-26T05:43:44 Z SirCovidThe19th Cake (CEOI14_cake) C++17
0 / 100
 693 ms 7044 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 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 238 ms 460 KB Output isn't correct
2 Incorrect 248 ms 588 KB Output isn't correct
3 Incorrect 240 ms 588 KB Output isn't correct
4 Incorrect 238 ms 588 KB Output isn't correct
5 Incorrect 255 ms 844 KB Output isn't correct
6 Incorrect 258 ms 872 KB Output isn't correct
7 Incorrect 252 ms 844 KB Output isn't correct
8 Incorrect 257 ms 872 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 207 ms 2912 KB Output isn't correct
2 Incorrect 207 ms 2744 KB Output isn't correct
3 Incorrect 199 ms 2536 KB Output isn't correct
4 Incorrect 0 ms 332 KB Output isn't correct
5 Incorrect 272 ms 5820 KB Output isn't correct
6 Incorrect 276 ms 5892 KB Output isn't correct
7 Incorrect 263 ms 5464 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 460 KB Output isn't correct
2 Incorrect 55 ms 564 KB Output isn't correct
3 Incorrect 105 ms 1532 KB Output isn't correct
4 Incorrect 103 ms 1516 KB Output isn't correct
5 Incorrect 166 ms 660 KB Output isn't correct
6 Incorrect 197 ms 1988 KB Output isn't correct
7 Incorrect 229 ms 996 KB Output isn't correct
8 Incorrect 142 ms 2372 KB Output isn't correct
9 Incorrect 693 ms 7044 KB Output isn't correct
10 Incorrect 581 ms 1516 KB Output isn't correct
11 Incorrect 550 ms 2096 KB Output isn't correct
12 Incorrect 647 ms 5784 KB Output isn't correct
13 Incorrect 668 ms 6868 KB Output isn't correct