답안 #392005

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
392005 2021-04-20T09:53:45 Z syl123456 케이크 (CEOI14_cake) C++17
0 / 100
582 ms 60016 KB
#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';
            }
        }
    }
}

Compilation message

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);
      |                 ~~^~~
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 582 ms 2504 KB Execution killed with signal 6
2 Runtime error 5 ms 2740 KB Execution killed with signal 11
3 Runtime error 17 ms 2772 KB Execution killed with signal 11
4 Correct 181 ms 1464 KB Output is correct
5 Runtime error 12 ms 6220 KB Execution killed with signal 11
6 Runtime error 11 ms 6320 KB Execution killed with signal 11
7 Runtime error 14 ms 6332 KB Execution killed with signal 11
8 Correct 190 ms 3148 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 53 ms 24384 KB Execution killed with signal 11
2 Runtime error 61 ms 24660 KB Execution killed with signal 6
3 Runtime error 44 ms 24252 KB Execution killed with signal 11
4 Runtime error 2 ms 332 KB Execution killed with signal 11
5 Correct 128 ms 30296 KB Output is correct
6 Correct 130 ms 30276 KB Output is correct
7 Runtime error 104 ms 60016 KB Execution killed with signal 11
# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 1100 KB Execution killed with signal 11
2 Runtime error 3 ms 1612 KB Execution killed with signal 6
3 Incorrect 112 ms 6396 KB Output isn't correct
4 Runtime error 20 ms 12296 KB Execution killed with signal 11
5 Runtime error 2 ms 844 KB Execution killed with signal 11
6 Incorrect 222 ms 8440 KB Output isn't correct
7 Incorrect 212 ms 1912 KB Output isn't correct
8 Runtime error 53 ms 24136 KB Execution killed with signal 11
9 Runtime error 114 ms 59880 KB Execution killed with signal 11
10 Runtime error 2 ms 848 KB Execution killed with signal 11
11 Runtime error 9 ms 5196 KB Execution killed with signal 11
12 Runtime error 93 ms 48052 KB Execution killed with signal 11
13 Runtime error 112 ms 59876 KB Execution killed with signal 11