답안 #391985

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391985 2021-04-20T09:22:48 Z syl123456 케이크 (CEOI14_cake) C++17
0 / 100
741 ms 30140 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 (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);
                    }
                }
            };
            continue;
            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 429 ms 1360 KB Output isn't correct
2 Incorrect 206 ms 1488 KB Output isn't correct
3 Incorrect 297 ms 1464 KB Output isn't correct
4 Incorrect 164 ms 1484 KB Output isn't correct
5 Incorrect 477 ms 3148 KB Output isn't correct
6 Incorrect 335 ms 3148 KB Output isn't correct
7 Incorrect 322 ms 3148 KB Output isn't correct
8 Incorrect 169 ms 3148 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 12184 KB Output isn't correct
2 Incorrect 43 ms 12220 KB Output isn't correct
3 Incorrect 41 ms 12208 KB Output isn't correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Incorrect 109 ms 29808 KB Output isn't correct
6 Incorrect 111 ms 29884 KB Output isn't correct
7 Incorrect 78 ms 29808 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 676 KB Output isn't correct
2 Incorrect 37 ms 928 KB Output isn't correct
3 Incorrect 83 ms 6204 KB Output isn't correct
4 Incorrect 91 ms 6224 KB Output isn't correct
5 Incorrect 130 ms 636 KB Output isn't correct
6 Incorrect 159 ms 8124 KB Output isn't correct
7 Incorrect 149 ms 1604 KB Output isn't correct
8 Incorrect 203 ms 12056 KB Output isn't correct
9 Incorrect 741 ms 30064 KB Output isn't correct
10 Incorrect 416 ms 964 KB Output isn't correct
11 Incorrect 496 ms 3112 KB Output isn't correct
12 Incorrect 700 ms 24508 KB Output isn't correct
13 Incorrect 438 ms 30140 KB Output isn't correct