답안 #391982

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391982 2021-04-20T09:21:18 Z syl123456 케이크 (CEOI14_cake) C++17
0 / 100
167 ms 30152 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;
            continue;
            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 (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()) {
                        if (-*--it <= pf) break;
                        rt.modify(-*it), hdl.erase(it);
                    }
                    it = next(x);
                    if (-*--it <= pf) f(!side);
                    else {
                        while (*(it = hdr.lower_bound(x)) != n - 1)
                            rt.modify(*it), hdr.erase(it);
                    }
                }
                else {
                    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()) {
                        if (*--it >= pf) break;
                        rt.modify(*it), hdl.erase(it);
                    }
                    it = next(x);
                    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;
            cout << "0\n";
            continue;
            --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 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 81 ms 1356 KB Output isn't correct
2 Incorrect 81 ms 1356 KB Output isn't correct
3 Incorrect 80 ms 1356 KB Output isn't correct
4 Incorrect 81 ms 1484 KB Output isn't correct
5 Incorrect 88 ms 3196 KB Output isn't correct
6 Incorrect 88 ms 3244 KB Output isn't correct
7 Incorrect 88 ms 3148 KB Output isn't correct
8 Incorrect 86 ms 3148 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 38 ms 12264 KB Output isn't correct
2 Incorrect 37 ms 12236 KB Output isn't correct
3 Incorrect 38 ms 12220 KB Output isn't correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Incorrect 74 ms 29828 KB Output isn't correct
6 Incorrect 76 ms 29848 KB Output isn't correct
7 Incorrect 72 ms 29860 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 716 KB Output isn't correct
2 Incorrect 10 ms 844 KB Output isn't correct
3 Incorrect 25 ms 6224 KB Output isn't correct
4 Incorrect 24 ms 6280 KB Output isn't correct
5 Incorrect 26 ms 596 KB Output isn't correct
6 Incorrect 40 ms 8060 KB Output isn't correct
7 Incorrect 34 ms 1572 KB Output isn't correct
8 Incorrect 55 ms 12048 KB Output isn't correct
9 Incorrect 145 ms 30128 KB Output isn't correct
10 Incorrect 85 ms 992 KB Output isn't correct
11 Incorrect 91 ms 3156 KB Output isn't correct
12 Incorrect 135 ms 24168 KB Output isn't correct
13 Incorrect 167 ms 30152 KB Output isn't correct