oj.uz

Submission #439242

# Submission time Handle Problem Language Result Execution time Memory
439242 2021-06-29T12:15:27 Z BeanZ Cake (CEOI14_cake) C++14
100 / 100
 688 ms 18332 KB 
// I_Love_LPL 11m
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 3e5 + 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]);
}
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;
    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("test.inp", "r", stdin);
        freopen("test.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;
            ll id = min(n, 10ll);
            for (int i = 1; i <= id; i++){
                if (pos[n - i + 1] == u){
                    id = i;
                    break;
                }
            }
            for (int i = id; 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;
            }
        }
    }
}
/*
7 2
3 7 6 5 2 1 4
5
E 5 1
E 6 3
E 6 1
E 1 5
F 4
Ans:

Out:
*/

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 8 ms 424 KB Output is correct
5 Correct 11 ms 916 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 5096 KB Output is correct
2 Correct 162 ms 5080 KB Output is correct
3 Correct 236 ms 5180 KB Output is correct
4 Correct 157 ms 5092 KB Output is correct
5 Correct 339 ms 5820 KB Output is correct
6 Correct 348 ms 6212 KB Output is correct
7 Correct 373 ms 6080 KB Output is correct
8 Correct 366 ms 6212 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 5812 KB Output is correct
2 Correct 81 ms 5780 KB Output is correct
3 Correct 69 ms 5676 KB Output is correct
4 Correct 1 ms 352 KB Output is correct
5 Correct 140 ms 11404 KB Output is correct
6 Correct 133 ms 11336 KB Output is correct
7 Correct 134 ms 11332 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 880 KB Output is correct
2 Correct 25 ms 972 KB Output is correct
3 Correct 58 ms 3280 KB Output is correct
4 Correct 77 ms 3236 KB Output is correct
5 Correct 89 ms 1728 KB Output is correct
6 Correct 155 ms 4952 KB Output is correct
7 Correct 103 ms 2816 KB Output is correct
8 Correct 137 ms 6376 KB Output is correct
9 Correct 688 ms 16200 KB Output is correct
10 Correct 305 ms 5204 KB Output is correct
11 Correct 383 ms 6744 KB Output is correct
12 Correct 608 ms 15068 KB Output is correct
13 Correct 493 ms 18332 KB Output is correct