oj.uz

Submission #491687

# Submission time Handle Problem Language Result Execution time Memory
491687 2021-12-03T19:51:03 Z Yazan_Alattar Cake (CEOI14_cake) C++14
0 / 100
 452 ms 6036 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};

priority_queue <int> pq;
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);
        pq.push(x);
        pos[x] = i;
    }
    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;
            vector <int> v;
            for(int i = 1; i < x; ++i){
                v.pb(pq.top());
                pq.pop();
            }
            int val = 1;
            if(pq.size()) val = pq.top() + 1;
            int val2 = val;
            while(!v.empty()){
                ++val;
                int p = pos[v.back()];
                v.pop_back();
                pos[val] = p;
                upd(p, val);
                pq.push(val);
            }
            pos[val2] = id;
            upd(id, val2);
        }
    }
    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 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 287 ms 576 KB Output isn't correct
2 Incorrect 163 ms 588 KB Output isn't correct
3 Incorrect 196 ms 600 KB Output isn't correct
4 Incorrect 94 ms 588 KB Output isn't correct
5 Incorrect 307 ms 892 KB Output isn't correct
6 Incorrect 264 ms 884 KB Output isn't correct
7 Incorrect 209 ms 824 KB Output isn't correct
8 Incorrect 102 ms 844 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 2820 KB Output isn't correct
2 Incorrect 63 ms 2596 KB Output isn't correct
3 Incorrect 62 ms 2664 KB Output isn't correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Incorrect 100 ms 5112 KB Output isn't correct
6 Incorrect 104 ms 5020 KB Output isn't correct
7 Incorrect 90 ms 4604 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 500 KB Output isn't correct
2 Incorrect 23 ms 532 KB Output isn't correct
3 Incorrect 55 ms 1612 KB Output isn't correct
4 Incorrect 62 ms 1584 KB Output isn't correct
5 Incorrect 84 ms 636 KB Output isn't correct
6 Incorrect 90 ms 1800 KB Output isn't correct
7 Incorrect 87 ms 1056 KB Output isn't correct
8 Incorrect 112 ms 2248 KB Output isn't correct
9 Incorrect 452 ms 6008 KB Output isn't correct
10 Incorrect 273 ms 1348 KB Output isn't correct
11 Incorrect 360 ms 2164 KB Output isn't correct
12 Incorrect 447 ms 5616 KB Output isn't correct
13 Incorrect 425 ms 6036 KB Output isn't correct