oj.uz

Submission #490273

# Submission time Handle Problem Language Result Execution time Memory
490273 2021-11-26T17:29:06 Z SirCovidThe19th Cake (CEOI14_cake) C++17
0 / 100
 533 ms 8928 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[11]; 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 <= 10; i++) rnk[i] = mQ * (11 - i); //rnk[i] = ith worst(most delicious) one
    for (int i = 1; i <= n; i++){
        int pos = tmp[i].second, r = (n - i + 1 > 0) ? rnk[n - i + 1] : i;
        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[e]);
            if (pos > a) R.upd(pos - a, ++rnk[e]);
        }
        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";
        }
    }
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:37:34: warning: unused variable 'r' [-Wunused-variable]
   37 |         int pos = tmp[i].second, r = (n - i + 1 > 0) ? rnk[n - i + 1] : i;
      |                                  ^

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 Runtime error 4 ms 844 KB Execution killed with signal 11
2 Runtime error 5 ms 1004 KB Execution killed with signal 11
3 Runtime error 4 ms 1100 KB Execution killed with signal 11
4 Runtime error 5 ms 844 KB Execution killed with signal 11
5 Runtime error 10 ms 1612 KB Execution killed with signal 11
6 Runtime error 9 ms 1500 KB Execution killed with signal 11
7 Runtime error 10 ms 1768 KB Execution killed with signal 11
8 Runtime error 9 ms 1484 KB Execution killed with signal 11

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 4160 KB Execution killed with signal 11
2 Runtime error 35 ms 2616 KB Execution killed with signal 11
3 Runtime error 35 ms 2656 KB Execution killed with signal 11
4 Incorrect 0 ms 332 KB Output isn't correct
5 Runtime error 94 ms 8924 KB Execution killed with signal 11
6 Runtime error 91 ms 8928 KB Execution killed with signal 11
7 Runtime error 88 ms 4976 KB Execution killed with signal 11

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 840 KB Output isn't correct
2 Incorrect 57 ms 864 KB Output isn't correct
3 Runtime error 18 ms 2500 KB Execution killed with signal 11
4 Runtime error 18 ms 1880 KB Execution killed with signal 11
5 Incorrect 166 ms 1280 KB Output isn't correct
6 Runtime error 23 ms 3012 KB Execution killed with signal 11
7 Runtime error 4 ms 1100 KB Execution killed with signal 11
8 Runtime error 35 ms 4056 KB Execution killed with signal 11
9 Runtime error 91 ms 8856 KB Execution killed with signal 11
10 Incorrect 533 ms 2076 KB Output isn't correct
11 Runtime error 8 ms 1356 KB Execution killed with signal 11
12 Runtime error 71 ms 7268 KB Execution killed with signal 11
13 Runtime error 92 ms 8824 KB Execution killed with signal 11