oj.uz

Submission #491691

# Submission time Handle Problem Language Result Execution time Memory
491691 2021-12-03T20:21:29 Z Yazan_Alattar Cake (CEOI14_cake) C++14
0 / 100
 566 ms 8184 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(a == 1 || a == n) cout << abs(a - x) << endl;
            else if(x > a){
                int res = get(a + 1, x), ans = x - a;
                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;
                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;
            reverse(all(v));
            while(!v.empty()){
                int cur = v.back();
                int p = pos[cur];
                v.pop_back();
                pos[cur + 1] = p;
                upd(p, cur + 1);
                pq.push(cur + 1);
            }
            pq.push(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 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 332 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 372 ms 4556 KB Output isn't correct
2 Correct 225 ms 4544 KB Output is correct
3 Correct 236 ms 4540 KB Output is correct
4 Correct 127 ms 4472 KB Output is correct
5 Incorrect 440 ms 4808 KB Output isn't correct
6 Incorrect 339 ms 6804 KB Output isn't correct
7 Correct 257 ms 6872 KB Output is correct
8 Correct 120 ms 6776 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 2764 KB Output is correct
2 Incorrect 85 ms 2624 KB Output isn't correct
3 Correct 56 ms 2620 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Correct 103 ms 5176 KB Output is correct
6 Incorrect 114 ms 5064 KB Output isn't correct
7 Correct 92 ms 4776 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 708 KB Output isn't correct
2 Correct 27 ms 844 KB Output is correct
3 Correct 58 ms 1860 KB Output is correct
4 Incorrect 89 ms 1908 KB Output isn't correct
5 Incorrect 116 ms 1476 KB Output isn't correct
6 Correct 96 ms 2832 KB Output is correct
7 Correct 111 ms 1852 KB Output is correct
8 Correct 136 ms 4492 KB Output is correct
9 Incorrect 548 ms 7952 KB Output isn't correct
10 Incorrect 411 ms 3504 KB Output isn't correct
11 Incorrect 448 ms 5140 KB Output isn't correct
12 Correct 566 ms 7620 KB Output is correct
13 Incorrect 472 ms 8184 KB Output isn't correct