| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 392388 |
2021-04-21T01:38:59 Z |
syl123456 |
Cake (CEOI14_cake) |
C++17 |
|
1970 ms |
31576 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) 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 + 1) 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 + 1) 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) 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);
if (it == hdl.begin()) {
f(!side);
return;
}
--it;
if (it != hdl.begin()) {
--it;
int _ = -*it;
while (!l.empty() && l.back() >= _) l.pop_back();
}
int _r = splay.rank(x);
while (!l.empty() && splay.rank(l.back()) > _r) l.pop_back();
int pf = l.empty() ? -1 : l.back();
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);
if (it == hdr.begin()) {
f(!side);
return;
}
--it;
if (it != hdr.begin()) {
--it;
int _ = *it;
while (!r.empty() && r.back() <= _) r.pop_back();
}
int _r = splay.rank(x);
while (!r.empty() && splay.rank(r.back()) > _r) r.pop_back();
int pf = r.empty() ? n : r.back();
while ((it = next(x)) != hdr.end()) {
--it;
if (*it >= pf) break;
rt.modify(*it), hdr.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);
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
312 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1086 ms |
1644 KB |
Output is correct |
| 2 |
Correct |
268 ms |
1764 KB |
Output is correct |
| 3 |
Correct |
1169 ms |
1856 KB |
Output is correct |
| 4 |
Correct |
190 ms |
1864 KB |
Output is correct |
| 5 |
Correct |
1372 ms |
3476 KB |
Output is correct |
| 6 |
Incorrect |
801 ms |
3472 KB |
Output isn't correct |
| 7 |
Correct |
1555 ms |
3508 KB |
Output is correct |
| 8 |
Correct |
195 ms |
3532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
12860 KB |
Output is correct |
| 2 |
Correct |
61 ms |
12744 KB |
Output is correct |
| 3 |
Incorrect |
58 ms |
12640 KB |
Output isn't correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
128 ms |
30576 KB |
Output is correct |
| 6 |
Correct |
131 ms |
30636 KB |
Output is correct |
| 7 |
Incorrect |
107 ms |
30388 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
1040 KB |
Output is correct |
| 2 |
Correct |
102 ms |
1220 KB |
Output is correct |
| 3 |
Correct |
206 ms |
6740 KB |
Output is correct |
| 4 |
Correct |
219 ms |
6612 KB |
Output is correct |
| 5 |
Correct |
318 ms |
1052 KB |
Output is correct |
| 6 |
Correct |
333 ms |
8640 KB |
Output is correct |
| 7 |
Correct |
330 ms |
2236 KB |
Output is correct |
| 8 |
Correct |
654 ms |
12340 KB |
Output is correct |
| 9 |
Correct |
1868 ms |
31524 KB |
Output is correct |
| 10 |
Correct |
1074 ms |
1916 KB |
Output is correct |
| 11 |
Correct |
1063 ms |
4292 KB |
Output is correct |
| 12 |
Correct |
1970 ms |
25768 KB |
Output is correct |
| 13 |
Correct |
1115 ms |
31576 KB |
Output is correct |
