oj.uz

Submission #438790

# Submission time Handle Problem Language Result Execution time Memory
438790 2021-06-28T15:26:30 Z BeanZ Cake (CEOI14_cake) C++14
0 / 100
 617 ms 12192 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 += 10;
            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 2 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 284 ms 664 KB Output isn't correct
2 Correct 149 ms 752 KB Output is correct
3 Correct 239 ms 716 KB Output is correct
4 Correct 146 ms 716 KB Output is correct
5 Incorrect 316 ms 1228 KB Output isn't correct
6 Incorrect 243 ms 1228 KB Output isn't correct
7 Correct 257 ms 1232 KB Output is correct
8 Correct 163 ms 1240 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 4488 KB Output is correct
2 Incorrect 74 ms 4416 KB Output isn't correct
3 Correct 77 ms 4260 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Correct 148 ms 8900 KB Output is correct
6 Incorrect 146 ms 9008 KB Output isn't correct
7 Correct 126 ms 8740 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 460 KB Output isn't correct
2 Correct 28 ms 576 KB Output is correct
3 Correct 64 ms 2240 KB Output is correct
4 Incorrect 72 ms 2304 KB Output isn't correct
5 Incorrect 86 ms 708 KB Output isn't correct
6 Correct 106 ms 3288 KB Output is correct
7 Correct 93 ms 1140 KB Output is correct
8 Correct 147 ms 4040 KB Output is correct
9 Incorrect 617 ms 9988 KB Output isn't correct
10 Incorrect 283 ms 1476 KB Output isn't correct
11 Incorrect 373 ms 2508 KB Output isn't correct
12 Correct 549 ms 9208 KB Output is correct
13 Incorrect 506 ms 12192 KB Output isn't correct