oj.uz

Submission #490292

# Submission time Handle Problem Language Result Execution time Memory
490292 2021-11-26T19:20:21 Z SirCovidThe19th Cake (CEOI14_cake) C++17
35 / 100
 2000 ms 4892 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; pair<int, int> tmp[mN]; DS<(1 << 19)> L, R;

deque<int> w10; int net = mN;

void ins(int pos, int v){
    if (pos < a) L.upd(a - pos, v);
    if (pos > a) R.upd(pos - a, v);
}
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++){
        int pos = tmp[i].second, r = i;
        if (i >= n - 9) r += mQ * 2, w10.push_back(pos);
        ins(pos, r);
    }
    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;
            auto it = find(w10.begin(), w10.end(), pos);
            if (it != w10.end()) w10.erase(it);
            w10.insert(w10.end() - e + 1, pos);
            if (w10.size() > 10) ins(w10[0], ++net);
            for (int i = 0; i < w10.size(); i++) ins(w10[i], mQ * 2 + i);
        }
        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:54:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             for (int i = 0; i < w10.size(); i++) ins(w10[i], mQ * 2 + i);
      |                             ~~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 308 KB Output is correct
4 Correct 89 ms 448 KB Output is correct
5 Correct 646 ms 680 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2091 ms 532 KB Time limit exceeded
2 Execution timed out 2090 ms 460 KB Time limit exceeded
3 Execution timed out 2083 ms 544 KB Time limit exceeded
4 Correct 683 ms 464 KB Output is correct
5 Execution timed out 2083 ms 784 KB Time limit exceeded
6 Execution timed out 2100 ms 716 KB Time limit exceeded
7 Execution timed out 2092 ms 716 KB Time limit exceeded
8 Correct 691 ms 716 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 2480 KB Output is correct
2 Correct 210 ms 2336 KB Output is correct
3 Correct 201 ms 2348 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 272 ms 4892 KB Output is correct
6 Correct 339 ms 4868 KB Output is correct
7 Correct 255 ms 4708 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 604 KB Time limit exceeded
2 Execution timed out 2074 ms 648 KB Time limit exceeded
3 Execution timed out 2084 ms 1356 KB Time limit exceeded
4 Execution timed out 2080 ms 1356 KB Time limit exceeded
5 Execution timed out 2070 ms 472 KB Time limit exceeded
6 Execution timed out 2075 ms 1484 KB Time limit exceeded
7 Execution timed out 2064 ms 604 KB Time limit exceeded
8 Execution timed out 2078 ms 1952 KB Time limit exceeded
9 Execution timed out 2048 ms 4344 KB Time limit exceeded
10 Execution timed out 2094 ms 564 KB Time limit exceeded
11 Execution timed out 2089 ms 964 KB Time limit exceeded
12 Execution timed out 2083 ms 3736 KB Time limit exceeded
13 Execution timed out 2088 ms 4456 KB Time limit exceeded