oj.uz

Submission #438786

# Submission time Handle Problem Language Result Execution time Memory
438786 2021-06-28T15:22:58 Z BeanZ Cake (CEOI14_cake) C++14
0 / 100
 569 ms 18116 KB 
// I_Love_LPL 11m
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 2e5 + 5;
long long mod = 998244353;
const int lim = 4e5 + 5;
const int lg = 22;
const int base = 311;
const long double eps = 1e-6;
ll a[N], pos[N], stR[N * 4], stL[N * 4];
ll n;
void updR(ll k, ll l, ll r, ll x, ll v){
    if (x > r || x < l) return;
    ll mid = (l + r) >> 1;
    if (l == r){
        stR[k] = v;
        return;
    }
    updR(k << 1, l, mid, x, v);
    updR(k << 1 | 1, mid + 1, r, x, v);
    stR[k] = max(stR[k << 1], stR[k << 1 | 1]);
}
void updL(ll k, ll l, ll r, ll x, ll v){
    if (x > r || x < l) return;
    ll mid = (l + r) >> 1;
    if (l == r){
        stL[k] = v;
        return;
    }
    updL(k << 1, l, mid, x, v);
    updL(k << 1 | 1, mid + 1, r, x, v);
    stL[k] = max(stL[k << 1], stL[k << 1 | 1]);
    //cout << stL[k] << endl;
}
ll getR(ll k, ll l, ll r, ll x, ll y){
    if (x > r || y < l) return 0;
    if (x <= l && y >= r) return stR[k];
    ll mid = (l + r) >> 1;
    return max(getR(k << 1, l, mid, x, y), getR(k << 1 | 1, mid + 1, r, x, y));
}
ll getL(ll k, ll l, ll r, ll x, ll y){
    if (x > r || y < l) return 0;
    //cout << "FUCKed" << " " << stL[k] << endl;
    if (x <= l && y >= r) return stL[k];
    ll mid = (l + r) >> 1;
    return max(getL(k << 1, l, mid, x, y), getL(k << 1 | 1, mid + 1, r, x, y));
}
ll getposR(ll k, ll l, ll r, ll v){
    ll mid = (l + r) >> 1;
    if (stR[k] < v) return n + 1;
    if (l == r) return l;
    if (stR[k << 1] >= v) return getposR(k << 1, l, mid, v);
    else return getposR(k << 1 | 1, mid + 1, r, v);
}
ll getposL(ll k, ll l, ll r, ll v){
    ll mid = (l + r) >> 1;
    if (stL[k] < v) return 0;
    if (l == r) return l;
    if (stL[k << 1 | 1] >= v) return getposL(k << 1 | 1, mid + 1, r, v);
    else return getposL(k << 1, l, mid, v);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("tests.inp", "r")){
        freopen("tests.inp", "r", stdin);
        freopen("tests.out", "w", stdout);
    }
    ll d;
    cin >> n >> d;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        if (i < d) updL(1, 1, d, i, a[i]);
        if (i > d) updR(1, d, n, i, a[i]);
        pos[a[i]] = i;
    }
    ll q;
    cin >> q;
    ll tt = n;
    while (q--){
        char task;
        cin >> task;
        if (task == 'E'){
            ll u, e;
            cin >> u >> e;
            for (int i = min(n, 10ll); i >= (e + 1); i--){
                pos[n - i + 1] = pos[n - i + 2];
            }
            pos[n - e + 1] = u;
            tt++;
            for (int i = 1; i <= e; i++){
                if (pos[n - i + 1] < d) updL(1, 1, d, pos[n - i + 1], tt - i + 1);
                if (pos[n - i + 1] > d) updR(1, d, n, pos[n - i + 1], tt - i + 1);
            }
        }
        else {
            ll u;
            cin >> u;
            if (u == d) cout << 0 << endl;
            else if (u < d){
                ll mx = getL(1, 1, d, u, d);
                ll id = getposR(1, d, n, mx);
                cout << id - u - 1 << endl;
            } else {
                ll mx = getR(1, d, n, d, u);
                ll id = getposL(1, 1, d, mx);
                cout << u - id - 1 << endl;
            }
        }
    }
}
/*
Ans:

Out:
*/

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen("tests.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen("tests.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 316 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 281 ms 4988 KB Output isn't correct
2 Correct 159 ms 5080 KB Output is correct
3 Correct 217 ms 5072 KB Output is correct
4 Correct 153 ms 5188 KB Output is correct
5 Incorrect 319 ms 6088 KB Output isn't correct
6 Incorrect 239 ms 6212 KB Output isn't correct
7 Correct 242 ms 6100 KB Output is correct
8 Correct 170 ms 6344 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 5820 KB Output is correct
2 Incorrect 74 ms 5768 KB Output isn't correct
3 Correct 71 ms 5652 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Runtime error 72 ms 15040 KB Execution killed with signal 11
6 Runtime error 75 ms 14916 KB Execution killed with signal 11
7 Runtime error 66 ms 14884 KB Execution killed with signal 11

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 868 KB Output isn't correct
2 Correct 26 ms 972 KB Output is correct
3 Correct 65 ms 3296 KB Output is correct
4 Incorrect 73 ms 3268 KB Output isn't correct
5 Incorrect 89 ms 1804 KB Output isn't correct
6 Correct 103 ms 4932 KB Output is correct
7 Correct 97 ms 2960 KB Output is correct
8 Correct 141 ms 6484 KB Output is correct
9 Runtime error 72 ms 15044 KB Execution killed with signal 11
10 Incorrect 287 ms 5144 KB Output isn't correct
11 Incorrect 389 ms 6740 KB Output isn't correct
12 Correct 569 ms 15044 KB Output is correct
13 Runtime error 77 ms 18116 KB Execution killed with signal 11