oj.uz

Submission #491689

# Submission time Handle Problem Language Result Execution time Memory
491689 2021-12-03T19:58:39 Z Yazan_Alattar Cake (CEOI14_cake) C++14
0 / 100
 475 ms 6076 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;
            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[val] = id;
            upd(id, val);
        }
    }
    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 332 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 288 ms 588 KB Output isn't correct
2 Incorrect 177 ms 584 KB Output isn't correct
3 Incorrect 194 ms 588 KB Output isn't correct
4 Incorrect 91 ms 588 KB Output isn't correct
5 Incorrect 334 ms 888 KB Output isn't correct
6 Incorrect 272 ms 844 KB Output isn't correct
7 Incorrect 216 ms 852 KB Output isn't correct
8 Incorrect 99 ms 892 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 2796 KB Output isn't correct
2 Incorrect 64 ms 2668 KB Output isn't correct
3 Incorrect 57 ms 2512 KB Output isn't correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Incorrect 105 ms 5104 KB Output isn't correct
6 Incorrect 107 ms 5204 KB Output isn't correct
7 Incorrect 90 ms 4652 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 456 KB Output isn't correct
2 Incorrect 23 ms 564 KB Output isn't correct
3 Incorrect 49 ms 1472 KB Output isn't correct
4 Incorrect 63 ms 1564 KB Output isn't correct
5 Incorrect 89 ms 724 KB Output isn't correct
6 Incorrect 91 ms 1844 KB Output isn't correct
7 Incorrect 88 ms 1016 KB Output isn't correct
8 Incorrect 111 ms 2252 KB Output isn't correct
9 Incorrect 468 ms 5996 KB Output isn't correct
10 Incorrect 290 ms 1388 KB Output isn't correct
11 Incorrect 373 ms 2088 KB Output isn't correct
12 Incorrect 475 ms 5520 KB Output isn't correct
13 Incorrect 427 ms 6076 KB Output isn't correct