제출 #392005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
392005		syl123456	케이크 (CEOI14_cake)	C++17	0 / 100	582 ms	60016 KiB

cake

#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
    return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
    i << '{' << j.size() << ':';
    for (T ii : j) i << ' ' << ii;
    return i << '}';
}
typedef long long ll;
typedef pair<int, int> pi;
struct Splay {
    vector<int> sz, pa;
    vector<array<int, 2>> ch;
    Splay(vector<int> a) {
        int n = a.size();
        sz.resize(n), pa.resize(n), ch.resize(n);
        for (int i = 0; i < n; ++i) {
            pa[a[i]] = i ? a[i - 1] : -1;
            ch[a[i]][1] = -1;
            ch[a[i]][0] = i < n - 1 ? a[i + 1] : -1;
            sz[a[i]] = n - i;
        }
    }
    void rotate(int i) {
        int p = pa[i], gp = pa[p], x = ch[p][1] == i, c = ch[i][!x];
        sz[p] -= sz[i], sz[i] += sz[p];
        if (~c) sz[p] += sz[c], pa[c] = p;
        ch[p][x] = c;
        pa[i] = gp;
        ch[i][!x] = p;
        pa[p] = i;
        if (~gp) ch[gp][ch[gp][1] == p] = i;
    }
    void splay(int i) {
        while (~pa[i]) {
            if (~pa[pa[i]]) {
                if (ch[pa[pa[i]]][1] == pa[i] ^ ch[pa[i]][1] == i)
                    rotate(i);
                else rotate(pa[i]);
            }
            rotate(i);
        }
    }
    int find(int i, int r) {
        if (i == -1) return -1;
        if (~ch[i][0]) {
            if (sz[ch[i][0]] == r - 1) return i;
            if (sz[ch[i][0]] < r - 1) return find(ch[i][1], r - sz[ch[i][0]] - 1);
            return find(ch[i][0], r);
        }
        if (r == 1) return i;
        return find(ch[i][1], r - 1);
    }
    void modify(int i, int r) {
        splay(i);
        int x = ch[i][0];
        while (~ch[x][1]) x = ch[x][1];
        pa[ch[i][0]] = -1;
        splay(x);
        if (~ch[i][1])
            ch[x][1] = ch[i][1], sz[x] += sz[ch[i][1]], pa[ch[i][1]] = x;
        ch[i][0] = ch[i][1] = -1, sz[i] = 1;
        x = find(x, r);
        if (x == -1) {
            x = i == 0 ? 1 : 0;
            splay(x);
            while (~ch[x][1]) x = ch[x][1];
            splay(x);
            ch[x][1] = i, pa[i] = x, ++sz[x];
        }
        else {
            splay(x);
            ch[i][0] = ch[x][0], pa[i] = x, ch[x][0] = i, ++sz[x];
            if (~ch[i][0]) pa[ch[i][0]] = i, sz[i] += sz[ch[i][0]];
        }
    }
    int rank(int i) {
        splay(i);
        return ~ch[i][0] ? sz[ch[i][0]] + 1 : 1;
    }
    vector<int> bigger(int i) {
        splay(i);
        vector<int> ans;
        put(ch[i][0], ans);
        ans.push_back(i);
        return ans;
    }
    void put(int i, vector<int> &v) {
        if (i == -1) return;
        put(ch[i][0], v), v.push_back(i), put(ch[i][1], v);
    }
};
struct seg {
    int l, r, v;
    seg *ch[2]{};
    seg(int _l, int _r) : l(_l), r(_r), v(0) {
        if (l < r - 1) ch[0] = new seg(l, l + r >> 1), ch[1] = new seg(l + r >> 1, r);
    }
    void modify(int i) {
        if (l == r - 1) {
            v = !v;
            return;
        }
        ch[i >= l + r >> 1]->modify(i);
        pull();
    }
    void pull() {
        v = ch[0]->v + ch[1]->v;
    }
    int presum(int i) {
        if (i <= l) return 0;
        if (i >= r) return v;
        int ans = ch[0]->presum(i);
        if (i > l + r >> 1) ans += ch[1]->presum(i);
        return ans;
    }
    int find(int i) {
        //pos of i-th 1
        //0th = 0, >now = n-1
        if (l == r - 1) return l;
        if (i > ch[0]->v)
            return ch[1]->find(i - ch[0]->v);
        return ch[0]->find(i);
    }
};
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, a;
    cin >> n >> a;
    --a;
    int d[n];
    vector<int> ord(n);
    for (int i = 0; i < n; ++i) cin >> d[i], ord[--d[i]] = i;
    Splay splay(ord);
    set<int> hdl, hdr;
    seg rt(0, n);
    for (int _l = a - 1, _r = a + 1; _l >= 0 || _r < n; ) {
        if (_l < 0) hdr.insert(n - 1), _r = n;
        else if (_r >= n) hdl.insert(0), _l = -1;
        else if (d[_l] < d[_r]) {
            if (_l == 0 || d[_l - 1] > d[_r]) hdl.insert(-_l);
            --_l;
        }
        else {
            if (_r == n - 1 || d[_r + 1] > d[_l]) hdr.insert(_r);
            ++_r;
        }
    }
    for (int i : hdl) rt.modify(-i);
    for (int i : hdr) rt.modify(i);
    auto next = [&](int x) {
        //it of next block
        if (splay.rank(a - 1) < splay.rank(a + 1)) {
            //rhs first
            if (x > a) {
                int h = *hdr.lower_bound(x);
                int mid = rt.presum(a);
                int tmp = rt.presum(h + 1) - mid;
                if (mid == tmp - 1) return hdl.end();
                return hdl.find(-rt.find(mid - tmp + 1));
            }
            else {
                int h = -*hdl.lower_bound(-x);
                int mid = rt.presum(a);
                int tmp = mid - rt.presum(h);
                if (rt.v - mid == tmp) return hdr.end();
                return hdr.find(rt.find(mid + tmp + 1));
            }
        }
        else {
            //lhs first
            if (x > a) {
                int h = *hdr.lower_bound(x);
                int mid = rt.presum(a);
                int tmp = rt.presum(h + 1) - mid;
                if (mid == tmp) return hdl.end();
                return hdl.find(-rt.find(mid - tmp));
            }
            else {
                int h = -*hdl.lower_bound(-x);
                int mid = rt.presum(a);
                int tmp = mid - rt.presum(h);
                if (rt.v - mid == tmp - 1) return hdr.end();
                return hdr.find(rt.find(mid + tmp));
            }
        }
    };
    int q;
    cin >> q;
    while (q--) {
        char ty;
        cin >> ty;
        if (ty == 'E') {
            int x, y;
            cin >> x >> y;
            if (a == 0 || a == n - 1) continue;
            --x;
            splay.modify(x, y);
            if (x == a) continue;
            vector<int> _big = splay.bigger(x);
            vector<int> l, r;
            for (int i : _big) {
                if (i > a) r.push_back(i);
                if (i < a) l.push_back(i);
            }
            sort(all(l)), sort(all(r), [](int i, int j){return i > j;});
            if (x < a) {
                while (l.back() != x) l.pop_back();
            }
            else {
                while (r.back() != x) r.pop_back();
            }
            function<void(bool)> f = [&](bool side) {
                int x = side ? r.back() : l.back();
                if (side) {
                    if (next(x) == hdl.end()) return ;
                    if (x - 1 > a && !hdr.count(x - 1))
                        rt.modify(x - 1), hdr.insert(x - 1);
                    auto it = next(x);
                    int _r = splay.rank(x);
                    if (it != hdl.begin()) {
                        --it;
                        if (it != hdl.begin()) {
                            --it;
                            int _ = -*it;
                            while (!l.empty() && l.back() >= _) l.pop_back();
                        }
                    }
                    while (!l.empty() && splay.rank(l.back()) > _r) l.pop_back();
                    int pf = l.empty() ? -1 : l.back();
                    if (next(x) == hdl.begin()) {
                        f(!side);
                        return;
                    }
                    while ((it = next(x)) != hdl.end()) {
                        --it;
                        if (-*it <= pf) break;
                        rt.modify(-*it), hdl.erase(it);
                    }
                    it = next(x);
                    --it;
                    if (-*it <= pf) f(!side);
                    else {
                        while (*(it = hdr.lower_bound(x)) != n - 1)
                            rt.modify(*it), hdr.erase(it);
                    }
                }
                else {
                    if (next(x) == hdr.end()) return ;
                    if (x + 1 < a && !hdl.count(-x - 1))
                        rt.modify(x + 1), hdl.insert(-x - 1);
                    auto it = next(x);
                    int _r = splay.rank(x);
                    if (it != hdr.begin()) {
                        --it;
                        if (it != hdr.begin()) {
                            --it;
                            int _ = *it;
                            while (!r.empty() && r.back() <= _) r.pop_back();
                        }
                    }
                    while (!r.empty() && splay.rank(r.back()) > _r) r.pop_back();
                    int pf = r.empty() ? n : r.back();
                    if (next(x) == hdr.begin()) {
                        f(!side);
                        return;
                    }
                    while ((it = next(x)) != hdr.end()) {
                        --it;
                        if (*it >= pf) break;
                        rt.modify(*it), hdl.erase(it);
                    }
                    it = next(x);
                    --it;
                    if (*it >= pf) f(!side);
                    else {
                        while (*(it = hdl.lower_bound(-x)) != 0)
                            rt.modify(-*it), hdl.erase(it);
                    }
                }
            };
            f(x > a);
        }
        else {
            int x;
            cin >> x;
            --x;
            if (x == a) {
                cout << "0\n";
                continue;
            }
            if (a == 0) {
                cout << x << '\n';
                continue;
            }
            if (a == n - 1) {
                cout << n - x - 1 << '\n';
                continue;
            }
            if (x > a) {
                auto it = next(x);
                int l = it == hdl.begin() ? a : -*--it;
                cout << x - l << '\n';
            }
            else {
                auto it = next(x);
                int r = it == hdr.begin() ? a : *--it;
                cout << r - x << '\n';
            }
        }
    }
}

컴파일 시 표준 에러 (stderr) 메시지

cake.cpp: In member function 'void Splay::splay(int)':
cake.cpp:43:38: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   43 |                 if (ch[pa[pa[i]]][1] == pa[i] ^ ch[pa[i]][1] == i)
cake.cpp: In constructor 'seg::seg(int, int)':
cake.cpp:103:45: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |         if (l < r - 1) ch[0] = new seg(l, l + r >> 1), ch[1] = new seg(l + r >> 1, r);
      |                                           ~~^~~
cake.cpp:103:74: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |         if (l < r - 1) ch[0] = new seg(l, l + r >> 1), ch[1] = new seg(l + r >> 1, r);
      |                                                                        ~~^~~
cake.cpp: In member function 'void seg::modify(int)':
cake.cpp:110:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |         ch[i >= l + r >> 1]->modify(i);
      |                 ~~^~~
cake.cpp: In member function 'int seg::presum(int)':
cake.cpp:120:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  120 |         if (i > l + r >> 1) ans += ch[1]->presum(i);
      |                 ~~^~~

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