oj.uz

Submission #491686

# Submission time Handle Problem Language Result Execution time Memory
491686 2021-12-03T19:40:34 Z Yazan_Alattar Cake (CEOI14_cake) C++14
0 / 100
 407 ms 6108 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <utility>
#include <cmath>
#include <numeric>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 250007;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

int n, a, q, seg[4 * M], cur, pos[4 * M];

void upd(int i, int v, int node = 1, int l = 1, int r = n)
{
    if(l == r){
        seg[node] = v;
        return;
    }
    int mid = (l + r) / 2;
    if(i <= mid) upd(i, v, 2 * node, l, mid);
    else upd(i, v, 2 * node + 1, mid + 1, r);
    seg[node] = max(seg[2 * node], seg[2 * node + 1]);
    return;
}

int get(int st, int en, int node = 1, int l = 1, int r = n)
{
    if(l > en || r < st) return 0;
    if(l >= st && r <= en) return seg[node];
    int mid = (l + r) / 2;
    return max(get(st, en, 2 * node, l, mid), get(st, en, 2 * node + 1, mid + 1, r));
}

int findr(int st, int en, int v, int node = 1, int l = 1, int r = n)
{
    if(l > en || r < st || seg[node] < v) return -1;
    if(l == r) return l;
    int mid = (l + r) / 2;
    int ret = findr(st, en, v, 2 * node + 1, mid + 1, r);
    if(ret == -1) ret = findr(st, en, v, 2 * node, l, mid);
    return ret;
}

int findl(int st, int en, int v, int node = 1, int l = 1, int r = n)
{
    if(l > en || r < st || seg[node] < v) return -1;
    if(l == r) return l;
    int mid = (l + r) / 2;
    int ret = findl(st, en, v, 2 * node, l, mid);
    if(ret == -1) ret = findl(st, en, v, 2 * node + 1, mid + 1, r);
    return ret;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> a;
    for(int i = 1; i <= n; ++i){
        int x;
        cin >> x;
        upd(i, x);
        pos[x] = i;
    }
    cur = n;
    cin >> q;
    while(q--){
        char c;
        cin >> c;
        if(c == 'F'){
            int x;
            cin >> x;
            if(x == a) cout << 0 << endl;
            else if(x > a){
                int res = get(a + 1, x), ans = x - a;
                if(a != 1){
                    int add = findr(1, a - 1, res);
                    if(add == -1) add = 0;
                    ans += a - add - 1;
                }
                cout << ans << endl;
            }
            else{
                int res = get(x, a - 1), ans = a - x;
                if(a != n){
                    int add = findl(a + 1, n, res);
                    if(add == -1) add = n + 1;
                    ans += add - a - 1;
                }
                cout << ans << endl;
            }
        }
        else{
            int id, x;
            cin >> id >> x;
            x = cur - x + 2;
            for(int i = cur; i >= x; --i){
                upd(pos[i], i + 1);
                pos[i + 1] = pos[i];
            }
            upd(id, x);
            pos[x] = id;
            ++cur;
        }
    }
    return 0;
}
// Don't forget special cases. (n = 1?)
// Look for the constraints. (Runtime array? overflow?)

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 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 189 ms 2556 KB Output isn't correct
2 Correct 127 ms 2480 KB Output is correct
3 Correct 147 ms 2508 KB Output is correct
4 Correct 94 ms 2492 KB Output is correct
5 Incorrect 213 ms 2708 KB Output isn't correct
6 Incorrect 184 ms 2732 KB Output isn't correct
7 Correct 161 ms 2720 KB Output is correct
8 Correct 104 ms 2752 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 2448 KB Output is correct
2 Incorrect 59 ms 2288 KB Output isn't correct
3 Correct 55 ms 2252 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Correct 97 ms 4116 KB Output is correct
6 Incorrect 92 ms 4072 KB Output isn't correct
7 Correct 86 ms 3908 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 652 KB Output isn't correct
2 Correct 22 ms 744 KB Output is correct
3 Correct 45 ms 1508 KB Output is correct
4 Incorrect 56 ms 1460 KB Output isn't correct
5 Incorrect 74 ms 1064 KB Output isn't correct
6 Correct 80 ms 1948 KB Output is correct
7 Correct 79 ms 1476 KB Output is correct
8 Correct 89 ms 2636 KB Output is correct
9 Incorrect 407 ms 5980 KB Output isn't correct
10 Incorrect 239 ms 2524 KB Output isn't correct
11 Incorrect 288 ms 3088 KB Output isn't correct
12 Correct 396 ms 5920 KB Output is correct
13 Incorrect 328 ms 6108 KB Output isn't correct