oj.uz

Submission #491690

# Submission time Handle Problem Language Result Execution time Memory
491690 2021-12-03T20:19:16 Z Yazan_Alattar Cake (CEOI14_cake) C++14
0 / 100
 607 ms 8040 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;
            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 421 ms 4540 KB Output isn't correct
2 Correct 235 ms 4552 KB Output is correct
3 Correct 261 ms 4504 KB Output is correct
4 Correct 113 ms 4548 KB Output is correct
5 Incorrect 385 ms 4808 KB Output isn't correct
6 Incorrect 364 ms 6928 KB Output isn't correct
7 Correct 289 ms 6868 KB Output is correct
8 Correct 120 ms 6760 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2756 KB Output is correct
2 Incorrect 61 ms 2736 KB Output isn't correct
3 Correct 60 ms 2624 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Correct 111 ms 5108 KB Output is correct
6 Incorrect 102 ms 5128 KB Output isn't correct
7 Correct 95 ms 4876 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 780 KB Output isn't correct
2 Correct 30 ms 844 KB Output is correct
3 Correct 64 ms 1800 KB Output is correct
4 Incorrect 77 ms 1860 KB Output isn't correct
5 Incorrect 116 ms 1476 KB Output isn't correct
6 Correct 111 ms 2952 KB Output is correct
7 Correct 105 ms 1860 KB Output is correct
8 Correct 127 ms 4544 KB Output is correct
9 Incorrect 599 ms 8040 KB Output isn't correct
10 Incorrect 377 ms 3452 KB Output isn't correct
11 Incorrect 473 ms 5032 KB Output isn't correct
12 Correct 607 ms 7656 KB Output is correct
13 Incorrect 476 ms 8028 KB Output isn't correct