oj.uz

Submission #491695

# Submission time Handle Problem Language Result Execution time Memory
491695 2021-12-03T21:28:21 Z Yazan_Alattar Cake (CEOI14_cake) C++14
100 / 100
 1026 ms 18828 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <utility>
#include <cmath>
#include <assert.h>
#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 = 500007;
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};

set <int> s;
int n, a, q, b[M], 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){
        cin >> b[i];
        upd(i, b[i]);
        s.insert(b[i]);
        pos[b[i]] = 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(*(--s.end()));
                s.erase(--s.end());
            }
            int val = 1;
            if(s.size()) val = *(--s.end()) + 1;
            reverse(all(v));
            while(!v.empty()){
                int cur = v.back();
                int p = pos[cur];
                v.pop_back();
                pos[cur + 1] = p;
                b[p] = cur + 1;
                upd(p, cur + 1);
                s.insert(cur + 1);
            }
            s.erase(b[id]);
            b[id] = val;
            s.insert(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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 444 KB Output is correct
5 Correct 17 ms 1176 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 2900 KB Output is correct
2 Correct 238 ms 2884 KB Output is correct
3 Correct 316 ms 2848 KB Output is correct
4 Correct 175 ms 2916 KB Output is correct
5 Correct 525 ms 3960 KB Output is correct
6 Correct 442 ms 3872 KB Output is correct
7 Correct 338 ms 3812 KB Output is correct
8 Correct 204 ms 3844 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 7412 KB Output is correct
2 Correct 78 ms 7200 KB Output is correct
3 Correct 69 ms 7248 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 214 ms 16624 KB Output is correct
6 Correct 202 ms 16740 KB Output is correct
7 Correct 140 ms 16544 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 680 KB Output is correct
2 Correct 34 ms 796 KB Output is correct
3 Correct 83 ms 3928 KB Output is correct
4 Correct 117 ms 3920 KB Output is correct
5 Correct 152 ms 1100 KB Output is correct
6 Correct 149 ms 5088 KB Output is correct
7 Correct 144 ms 1880 KB Output is correct
8 Correct 200 ms 7584 KB Output is correct
9 Correct 1026 ms 18800 KB Output is correct
10 Correct 468 ms 2440 KB Output is correct
11 Correct 587 ms 4076 KB Output is correct
12 Correct 959 ms 16048 KB Output is correct
13 Correct 723 ms 18828 KB Output is correct