| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 286800 |
2020-08-30T23:54:18 Z |
fishy15 |
Cake (CEOI14_cake) |
C++17 |
|
570 ms |
8448 KB |
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>
#define ll long long
#define ld long double
#define eps 1e-8
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
// change if necessary
#define MAXN 250010
using namespace std;
int n, a;
int q;
int st[4 * MAXN];
int nums[MAXN];
int sz;
vector<int> top;
int curmax;
void build(int v, int l, int r) {
if (l == r) {
st[v] = nums[l];
} else {
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
st[v] = max(st[2 * v], st[2 * v + 1]);
}
}
void upd(int v, int l, int r, int x, int y) {
if (l == r) {
st[v] = y;
nums[x] = y;
} else {
int m = (l + r) / 2;
if (x <= m) {
upd(2 * v, l, m, x, y);
} else {
upd(2 * v + 1, m + 1, r, x, y);
}
st[v] = max(st[2 * v], st[2 * v + 1]);
}
}
int qry_max(int v, int l, int r, int x, int y) {
if (x <= l && r <= y) {
return st[v];
} else if (y < l || x > r) {
return 0;
} else {
int m = (l + r) / 2;
return max(qry_max(2 * v, l, m, x, y), qry_max(2 * v + 1, m + 1, r, x, y));
}
}
int qry_left(int v, int l, int r, int mm) {
if (st[v] <= mm) {
return l;
} else {
if (l == r) {
return -1;
} else {
int m = (l + r) / 2;
if (m + 1 > a) return qry_left(2 * v, l, m, mm);
if (st[2 * v + 1] <= mm) {
int v1 = qry_left(2 * v, l, m, mm);
if (v1 == -1) return m + 1;
return v1;
} else {
return qry_left(2 * v + 1, m + 1, r, mm);
}
}
}
}
int qry_right(int v, int l, int r, int mm) {
if (st[v] <= mm) {
return r;
} else {
if (l == r) {
return -1;
} else {
int m = (l + r) / 2;
if (a > m) return qry_right(2 * v + 1, m + 1, r, mm);
if (st[2 * v] <= mm) {
int v1 = qry_right(2 * v + 1, m + 1, r, mm);
if (v1 == -1) return m;
return v;
} else {
return qry_right(2 * v, l, m, mm);
}
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> a;
a--;
curmax = n;
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
sz = min(n, 10);
top.resize(sz);
for (int i = 0; i < n; i++) {
if (nums[i] > n - sz) {
top[n - nums[i]] = i;
}
}
build(1, 0, n - 1);
cin >> q;
while (q--) {
char t; cin >> t;
if (t == 'F') {
int x; cin >> x;
x--;
if (x < a) {
int ans = a - x;
int mm = qry_max(1, 0, n - 1, x, a);
ans += qry_right(1, 0, n - 1, mm) - a;
cout << ans << '\n';
} else if (x > a) {
int ans = x - a;
int mm = qry_max(1, 0, n - 1, a, x);
ans += a - qry_left(1, 0, n - 1, mm);
cout << ans << '\n';
} else {
cout << "0\n";
}
} else {
int i, e; cin >> i >> e;
i--; e--;
auto it = find(top.begin(), top.end(), i);
if (it != top.end()) {
top.erase(it);
}
top.insert(top.begin() + e, i);
if (top.size() > sz) top.pop_back();
for (int j = 1; j <= sz; j++) {
upd(1, 0, n - 1, top[n - j], curmax + j);
}
curmax += sz;
}
}
return 0;
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:162:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
162 | if (top.size() > sz) top.pop_back();
| ~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
515 ms |
5020 KB |
Output isn't correct |
| 2 |
Incorrect |
518 ms |
4920 KB |
Output isn't correct |
| 3 |
Incorrect |
517 ms |
5032 KB |
Output isn't correct |
| 4 |
Incorrect |
518 ms |
4988 KB |
Output isn't correct |
| 5 |
Incorrect |
567 ms |
5368 KB |
Output isn't correct |
| 6 |
Incorrect |
562 ms |
5756 KB |
Output isn't correct |
| 7 |
Incorrect |
570 ms |
5616 KB |
Output isn't correct |
| 8 |
Incorrect |
564 ms |
5880 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
4096 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
14 ms |
4120 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
13 ms |
4096 KB |
Execution killed with signal 11 |
| 4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 5 |
Runtime error |
33 ms |
8440 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
35 ms |
8348 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
31 ms |
8312 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
896 KB |
Output isn't correct |
| 2 |
Incorrect |
37 ms |
1016 KB |
Output isn't correct |
| 3 |
Runtime error |
8 ms |
2432 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
7 ms |
2432 KB |
Execution killed with signal 11 |
| 5 |
Incorrect |
95 ms |
1788 KB |
Output isn't correct |
| 6 |
Runtime error |
9 ms |
2688 KB |
Execution killed with signal 11 |
| 7 |
Incorrect |
151 ms |
2552 KB |
Output isn't correct |
| 8 |
Runtime error |
13 ms |
4096 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
33 ms |
8448 KB |
Execution killed with signal 11 |
| 10 |
Incorrect |
309 ms |
5076 KB |
Output isn't correct |
| 11 |
Incorrect |
419 ms |
6264 KB |
Output isn't correct |
| 12 |
Runtime error |
27 ms |
7672 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
32 ms |
8312 KB |
Execution killed with signal 11 |
