| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 101431 |
2019-03-19T01:51:24 Z |
lyc |
Cake (CEOI14_cake) |
C++14 |
|
1732 ms |
152684 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
struct node {
int s, e, m; vector<int> v;
node *l, *r;
node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2) {
if (s != e) {
l = new node(s, m);
r = new node(m+1, e);
}
}
void def(int i, int x) {
if (s == e) { v.clear(); v.push_back(x); }
else if (i <= m) l->def(i, x);
else r->def(i, x);
}
void build() {
if (s == e) return;
l->build();
r->build();
for (int i = 0, j = 0; i < SZ(l->v) || j < SZ(r->v);) {
if (i < SZ(l->v) && (j == SZ(r->v) || l->v[i] <= r->v[j])) v.push_back(l->v[i++]);
else v.push_back(r->v[j++]);
}
//cout << s << " " << e << " : ";
//for (auto x : v) cout << x << " "; cout << endl;
}
void update(int i, int ov, int nv) {
//cout << "UPDATE " << i << " " << nv << endl;
//cout << '\t'; for (auto y : v) cout << y << " "; cout << endl;
if (s != e) {
if (i <= m) l->update(i, ov, nv);
else r->update(i, ov, nv);
}
stack<int> s;
while (v.back() != ov) {
s.push(v.back());
v.pop_back();
assert(!v.empty());
}
v.pop_back();
while (!s.empty() && s.top() < nv) {
v.push_back(s.top());
s.pop();
}
v.push_back(nv);
while (!s.empty()) {
v.push_back(s.top());
s.pop();
}
}
void increase(int x) {
if (s != e) {
if (l->v.back() >= x) l->increase(x);
if (r->v.back() >= x) r->increase(x);
}
//cout << "INCREASING " << s << " " << e << endl;
for (int i = SZ(v)-1; i >= 0 && v[i] >= x; --i) {
++v[i];
}
//cout << '\t'; for (auto y : v) cout <<y << " " ; cout<< endl;
}
ll qmax(int x, int y) {
//cout << "QMAX " << x << " " << y << " of " << s << " " << e << endl;
if (s == x && e == y) { assert(!v.empty()); return v.back(); }
else if (y <= m) return l->qmax(x, y);
else if (x > m) return r->qmax(x, y);
else return max(l->qmax(x, m), r->qmax(m+1, y));
}
int qcntless(int x, int y, int z) {
if (s == x && e == y) return lower_bound(ALL(v), z) - v.begin();
else if (y <= m) return l->qcntless(x, y, z);
else if (x > m) return r->qcntless(x, y, z);
else return l->qcntless(x, m, z) + r->qcntless(m+1, y, z);
}
void dbg() {
}
} *root;
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int n, a; cin >> n >> a;
int d[n+1];
root = new node(1, n);
set<int> delival;
for (int i = 1; i <= n; ++i) {
cin >> d[i];
d[i] *= 500000;
root->def(i, d[i]);
delival.insert(d[i]);
}
root->build();
int q; cin >> q;
for (int qi = 0; qi < q; ++qi) {
char t; cin >> t;
if (t == 'F') {
int b; cin >> b;
//cout << "HI" << endl;
if (b == a) cout << 0 << '\n';
else if (b < a) {
//cout << "CASE 1: " << endl;
int maxi = root->qmax(b, a-1);
//cout << maxi << endl;
int cnt = root->qcntless(a+1, n, maxi);
cout << cnt + (a-b) << '\n';
}
else {
int maxi = root->qmax(a+1, b);
//cout << "MAXI " << maxi << endl;
int cnt = root->qcntless(1, a-1, maxi);
cout << cnt + (b-a) << '\n';
}
}
else {
int i, e; cin >> i >> e;
//cout << "OVAL " << d[i] << endl;
//for (auto x : delival) cout << x << " "; cout << endl;
ll ov = d[i];
delival.erase(d[i]);
auto it = delival.end();
for (it = prev(it); e > 1; --e) {
auto jt = prev(it);
delival.insert(*it+1);
delival.erase(it);
it = jt;
}
//if (d[i] == *it) continue;
d[i] = *it+1;
delival.insert(d[i]);
//cout << "NVAL " << d[i] << endl;
//for (auto x : delival) cout << x << " "; cout << endl;
root->increase(d[i]);
root->update(i, ov, d[i]);
}
//cout << flush;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
6272 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
17 ms |
6784 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
21 ms |
6784 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
740 ms |
6976 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
39 ms |
15480 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
33 ms |
15608 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
51 ms |
15608 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
753 ms |
15608 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
382 ms |
32020 KB |
Output isn't correct |
| 2 |
Runtime error |
192 ms |
62580 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
216 ms |
62632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
3 ms |
384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Incorrect |
851 ms |
77116 KB |
Output isn't correct |
| 6 |
Runtime error |
628 ms |
152684 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
518 ms |
151780 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
2304 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
13 ms |
3584 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
200 ms |
31348 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
122 ms |
31220 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
8 ms |
1636 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
847 ms |
39152 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
35 ms |
6784 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
245 ms |
62420 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
735 ms |
152564 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
7 ms |
1664 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
55 ms |
13176 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
1732 ms |
126052 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
618 ms |
151788 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
