Submission #391986

# Submission time Handle Problem Language Result Execution time Memory
391986 2021-04-20T09:23:27 Z syl123456 Cake (CEOI14_cake) C++17
0 / 100
906 ms 31412 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;
            --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);
      |                 ~~^~~
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 428 ms 1356 KB Output isn't correct
2 Incorrect 190 ms 1484 KB Output isn't correct
3 Incorrect 303 ms 1356 KB Output isn't correct
4 Correct 164 ms 1484 KB Output is correct
5 Incorrect 454 ms 3148 KB Output isn't correct
6 Incorrect 350 ms 3148 KB Output isn't correct
7 Incorrect 322 ms 3148 KB Output isn't correct
8 Correct 170 ms 3240 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 12568 KB Output isn't correct
2 Incorrect 59 ms 12476 KB Output isn't correct
3 Incorrect 57 ms 12404 KB Output isn't correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Incorrect 129 ms 30272 KB Output isn't correct
6 Incorrect 141 ms 30320 KB Output isn't correct
7 Incorrect 106 ms 30088 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 712 KB Output isn't correct
2 Incorrect 45 ms 948 KB Output isn't correct
3 Incorrect 96 ms 6392 KB Output isn't correct
4 Incorrect 111 ms 6632 KB Output isn't correct
5 Incorrect 155 ms 956 KB Output isn't correct
6 Incorrect 193 ms 8384 KB Output isn't correct
7 Incorrect 191 ms 1988 KB Output isn't correct
8 Incorrect 205 ms 12024 KB Output isn't correct
9 Incorrect 878 ms 31264 KB Output isn't correct
10 Incorrect 508 ms 1572 KB Output isn't correct
11 Incorrect 600 ms 3908 KB Output isn't correct
12 Incorrect 906 ms 25548 KB Output isn't correct
13 Incorrect 554 ms 31412 KB Output isn't correct