oj.uz

Submission #491681

# Submission time Handle Problem Language Result Execution time Memory
491681 2021-12-03T19:16:42 Z Yazan_Alattar Cake (CEOI14_cake) C++14
0 / 100
 402 ms 12356 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;
                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;
                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 1 ms 208 KB Output is correct
2 Incorrect 1 ms 336 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 199 ms 6836 KB Output isn't correct
2 Correct 130 ms 6760 KB Output is correct
3 Correct 147 ms 6820 KB Output is correct
4 Correct 97 ms 6860 KB Output is correct
5 Incorrect 221 ms 7360 KB Output isn't correct
6 Incorrect 191 ms 7620 KB Output isn't correct
7 Correct 163 ms 7436 KB Output is correct
8 Correct 113 ms 7624 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 3612 KB Output is correct
2 Incorrect 58 ms 3444 KB Output isn't correct
3 Correct 51 ms 3452 KB Output is correct
4 Incorrect 0 ms 336 KB Output isn't correct
5 Correct 94 ms 6428 KB Output is correct
6 Incorrect 101 ms 6412 KB Output isn't correct
7 Correct 83 ms 6180 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 908 KB Output isn't correct
2 Correct 22 ms 1028 KB Output is correct
3 Correct 46 ms 2296 KB Output is correct
4 Incorrect 61 ms 2244 KB Output isn't correct
5 Incorrect 72 ms 1972 KB Output isn't correct
6 Correct 82 ms 3400 KB Output is correct
7 Correct 77 ms 2900 KB Output is correct
8 Correct 91 ms 5044 KB Output is correct
9 Incorrect 397 ms 12284 KB Output isn't correct
10 Incorrect 232 ms 6076 KB Output isn't correct
11 Incorrect 294 ms 7172 KB Output isn't correct
12 Correct 402 ms 11592 KB Output is correct
13 Incorrect 327 ms 12356 KB Output isn't correct