Submission #1123442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123442		kh0i	Cake (CEOI14_cake)	C++20	0 / 100	460 ms	10108 KiB

cake

#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;
using pii = pair<int, int>;

#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

const int N = 250003;

int n, q, d[N], pos[N];
vector<pii> val;
int a;

namespace ST{
    int st[N << 2];

    void _update(int id, int l, int r, int pos, int val){
        if(l == r){
            st[id] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if(pos <= mid)
            _update(id << 1, l, mid, pos, val);
        else
            _update(id << 1 | 1, mid + 1, r, pos, val);
        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }

    int _get(int id, int l, int r, int tl, int tr){
        if(l > tr or tl > r)
            return 0;
        if(tl <= l and r <= tr)
            return st[id];
        int mid = (l + r) >> 1;
        return max(_get(id << 1, l, mid, tl, tr), _get(id << 1 | 1, mid + 1, r, tl, tr));
    }

    int _walkl(int id, int l, int r, int tl, int tr, int val){
        if(l > tr or tl > r)
            return -1;
        if(st[id] < val)
            return -1;
        if(l == r)
            return l;
        int mid = (l + r) >> 1;
        int res = _walkl(id << 1, l, mid, tl, tr, val);
        if(res != -1)
            return res;
        return _walkl(id << 1 | 1, mid + 1, r, tl, tr, val);
    }

    int _walkr(int id, int l, int r, int tl, int tr, int val){
        if(l > tr or tl > r)
            return -1;
        if(st[id] < val)
            return -1;
        if(l == r)
            return l;
        int mid = (l + r) >> 1;
        int res = _walkr(id << 1 | 1, mid + 1, r, tl, tr, val);
        if(res != -1)
            return res;
        return _walkr(id << 1, l, mid, tl, tr, val);
    }

    void update(int pos, int val){ _update(1, 1, n, pos, val); }
    int get(int l, int r){ return _get(1, 1, n, l, r); }
    int walkl(int l, int r, int val){ return _walkl(1, 1, n, l, r, val); }
    int walkr(int l, int r, int val){ return _walkr(1, 1, n, l, r, val); }
}

void solve(){
    cin >> n >> a;
    for(int i = 1; i <= n; ++i){
        cin >> d[i];
        pos[d[i]] = i;
    }
    for(int i = 1; i <= n; ++i){
        val.emplace_back(i, pos[i]);
        ST::update(i, d[i]);
    }
    cin >> q;
    while(q--){
        char c;
        cin >> c;
        if(c == 'E'){
            int i, e;
            cin >> i >> e;
            set<int> saved;
            vector<pii> nx;
            while(sz(nx) + 1 < e){
                if(!saved.count(val.back().S)){
                    nx.push_back(val.back());
                    saved.insert(val.back().S);
                }
                val.pop_back();
            }
            ST::update(i, val.back().F + 1);
            val.emplace_back(val.back().F + 1, i);
            reverse(all(nx));
            while(!nx.empty()){
                ST::update(nx.back().S, val.back().F + 1);
                val.emplace_back(val.back().F + 1, nx.back().S);
                nx.pop_back();
            }
        }
        else{
            int b;
            cin >> b;
            if(b == a){
                cout << 0 << '\n';
                continue;
            }
            if(a == 1 or a == n){
                cout << abs(a - b) << '\n';
                continue;
            }
            if(b < a){
                int mx = ST::get(b, a - 1);
                int rv = ST::walkl(a + 1, n, mx);
                if(rv == -1)
                    rv = n + 1;
                cout << rv - b - 1 << '\n';
            }
            else{
                int mx = ST::get(a + 1, b);
                int lv = ST::walkr(1, a - 1, mx);
                if(lv == -1)
                    lv = 0;
                cout << b - lv - 1 << '\n';
            }
        }
    }
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    #define task "troll"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int test = 1;
//    cin >> test;
    for(int i = 1; i <= test; ++i){
//        cout << "Case #" << i << ": ";
        solve();
    }
    #ifdef LOCAL
        cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    #endif
    return 0;
}

Compilation message (stderr)

cake.cpp: In function 'int32_t main()':
cake.cpp:157:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cake.cpp:158:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50