oj.uz

Submission #491682

# Submission time Handle Problem Language Result Execution time Memory
491682 2021-12-03T19:20:58 Z Yazan_Alattar Cake (CEOI14_cake) C++14
0 / 100
 402 ms 6012 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) ans += a - 1;
                    else 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) ans += n - a;
                    else ans += add - a - 1;
                }
                cout << ans << endl;
            }
        }
        else{
            int id, x;
            cin >> id >> x;
            x = cur + 1 - x + 1;
            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 0 ms 204 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 231 ms 2316 KB Output isn't correct
2 Correct 129 ms 2388 KB Output is correct
3 Correct 140 ms 2388 KB Output is correct
4 Correct 104 ms 2356 KB Output is correct
5 Incorrect 231 ms 2596 KB Output isn't correct
6 Incorrect 189 ms 2516 KB Output isn't correct
7 Correct 161 ms 2584 KB Output is correct
8 Correct 122 ms 2584 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 2316 KB Output is correct
2 Incorrect 60 ms 2200 KB Output isn't correct
3 Correct 55 ms 2156 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Correct 114 ms 3956 KB Output is correct
6 Incorrect 96 ms 3940 KB Output isn't correct
7 Correct 86 ms 3708 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 460 KB Output isn't correct
2 Correct 22 ms 560 KB Output is correct
3 Correct 54 ms 1268 KB Output is correct
4 Incorrect 69 ms 1272 KB Output isn't correct
5 Incorrect 72 ms 876 KB Output isn't correct
6 Correct 82 ms 1728 KB Output is correct
7 Correct 78 ms 1340 KB Output is correct
8 Correct 87 ms 2512 KB Output is correct
9 Incorrect 396 ms 5924 KB Output isn't correct
10 Incorrect 239 ms 2372 KB Output isn't correct
11 Incorrect 327 ms 2960 KB Output isn't correct
12 Correct 402 ms 5672 KB Output is correct
13 Incorrect 349 ms 6012 KB Output isn't correct