oj.uz

Submission #491688

# Submission time Handle Problem Language Result Execution time Memory
491688 2021-12-03T19:55:59 Z Yazan_Alattar Cake (CEOI14_cake) C++14
0 / 100
 544 ms 6044 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 + v.size();
            reverse(all(v));
            while(!v.empty()){
                int p = pos[v.back()];
                v.pop_back();
                pos[val] = p;
                upd(p, val);
                pq.push(val);
                --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 1 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 330 ms 588 KB Output isn't correct
2 Incorrect 165 ms 588 KB Output isn't correct
3 Incorrect 197 ms 588 KB Output isn't correct
4 Incorrect 102 ms 708 KB Output isn't correct
5 Incorrect 352 ms 844 KB Output isn't correct
6 Incorrect 278 ms 884 KB Output isn't correct
7 Incorrect 219 ms 892 KB Output isn't correct
8 Incorrect 123 ms 892 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 2820 KB Output isn't correct
2 Incorrect 59 ms 2624 KB Output isn't correct
3 Incorrect 55 ms 2616 KB Output isn't correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Incorrect 107 ms 5028 KB Output isn't correct
6 Incorrect 110 ms 5072 KB Output isn't correct
7 Incorrect 88 ms 4800 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 460 KB Output isn't correct
2 Incorrect 32 ms 612 KB Output isn't correct
3 Incorrect 66 ms 1448 KB Output isn't correct
4 Incorrect 94 ms 1608 KB Output isn't correct
5 Incorrect 104 ms 684 KB Output isn't correct
6 Incorrect 89 ms 1912 KB Output isn't correct
7 Incorrect 89 ms 972 KB Output isn't correct
8 Incorrect 114 ms 2268 KB Output isn't correct
9 Incorrect 525 ms 6024 KB Output isn't correct
10 Runtime error 320 ms 1608 KB Execution killed with signal 11
11 Incorrect 398 ms 2340 KB Output isn't correct
12 Incorrect 544 ms 5584 KB Output isn't correct
13 Incorrect 456 ms 6044 KB Output isn't correct