oj.uz

Submission #438788

# Submission time Handle Problem Language Result Execution time Memory
438788 2021-06-28T15:24:04 Z BeanZ Cake (CEOI14_cake) C++14
0 / 100
 646 ms 16840 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]);
    //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 332 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 285 ms 660 KB Output isn't correct
2 Correct 169 ms 836 KB Output is correct
3 Correct 217 ms 740 KB Output is correct
4 Correct 152 ms 716 KB Output is correct
5 Incorrect 330 ms 1348 KB Output isn't correct
6 Incorrect 246 ms 1228 KB Output isn't correct
7 Correct 249 ms 1228 KB Output is correct
8 Correct 170 ms 1356 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 4520 KB Output is correct
2 Incorrect 83 ms 4292 KB Output isn't correct
3 Correct 71 ms 4360 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Correct 171 ms 9884 KB Output is correct
6 Incorrect 131 ms 9840 KB Output isn't correct
7 Correct 114 ms 9732 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 460 KB Output isn't correct
2 Correct 31 ms 588 KB Output is correct
3 Correct 65 ms 2276 KB Output is correct
4 Incorrect 73 ms 2300 KB Output isn't correct
5 Incorrect 90 ms 708 KB Output isn't correct
6 Correct 124 ms 3248 KB Output is correct
7 Correct 104 ms 1236 KB Output is correct
8 Correct 145 ms 3916 KB Output is correct
9 Incorrect 646 ms 14740 KB Output isn't correct
10 Incorrect 294 ms 1476 KB Output isn't correct
11 Incorrect 392 ms 2472 KB Output isn't correct
12 Correct 602 ms 9116 KB Output is correct
13 Incorrect 485 ms 16840 KB Output isn't correct