| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 90821 |
2018-12-24T15:26:50 Z |
EntityIT |
Cake (CEOI14_cake) |
C++14 |
|
370 ms |
6728 KB |
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
typedef pair<int, int> ii;
const int N = 250005, inf = 1e9 + 123;
int n, start, q, cur;
ii pos[11];
vector<int> a[2];
struct It {
int node[N << 2];
void build_tree (bool _, int nd, int Left, int Right) {
if (Left == Right) {
node[nd] = a[_][Left];
return ;
}
int mid = Left + Right >> 1;
build_tree(_, nd << 1, Left, mid); build_tree(_, nd << 1 | 1, mid + 1, Right);
node[nd] = max(node[nd << 1], node[nd << 1 | 1]);
}
void update (int nd, int Left, int Right, int pos, int val) {
if (pos < Left || Right < pos) return ;
if (Left == Right) { node[nd] = val; return ; }
int mid = Left + Right >> 1;
update(nd << 1, Left, mid, pos, val); update(nd << 1 | 1, mid + 1, Right, pos, val);
node[nd] = max(node[nd << 1], node[nd << 1 | 1]);
}
int get (int nd, int Left, int Right, int l, int r) {
// cout << "l = " << l << " r = " << r << '\n';
if (Right < l || r < Left) return 0;
if (l <= Left && Right <= r) return node[nd];
int mid = Left + Right >> 1;
return max(get(nd << 1, Left, mid, l, r), get(nd << 1 | 1, mid + 1, Right, l, r) );
}
int getPos (int nd, int Left, int Right, int val) {
if (Left == Right) return Left;
int mid = Left + Right >> 1;
if (node[nd << 1] > val) return getPos(nd << 1, Left, mid, val);
else return getPos(nd << 1 | 1, mid + 1, Right, val);
}
} it[2];
ii getRealPos (int b) {
if (b == start) return ii(-1, -1);
if (b > start) return ii(1, b - start - 1);
return ii(0, start - b - 1);
}
int main () {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("cake.in", "r", stdin);
cin >> n >> start; cur = n;
for (int i = 1; i <= n; ++i) {
int inp; cin >> inp;
if (n - inp + 1 <= 10) pos[n - inp + 1] = getRealPos(i);
if (i < start) a[0].pb(inp);
else if (i > start) a[1].pb(inp);
}
reverse(a[0].begin(), a[0].end() );
a[0].pb(inf);
a[1].pb(inf);
// for (auto _ : a[0]) cout << _ << ' '; cout << '\n';
// for (auto _ : a[1]) cout << _ << ' '; cout << '\n';
// for (int i = 1; i <= min(10, n); ++i) cout << pos[i].fi << '-' << pos[i].se << ' '; cout << '\n';
it[0].build_tree(0, 1, 0, (int)a[0].size() - 1);
it[1].build_tree(1, 1, 0, (int)a[1].size() - 1);
cin >> q;
while (q --) {
char c; int b; cin >> c >> b;
ii realPos = getRealPos(b);
if (c == 'F') {
if (realPos == ii(-1, -1) ) cout << "0\n";
else cout << realPos.se +
it[realPos.fi ^ 1].getPos(1, 0, (int)a[realPos.fi ^ 1].size() - 1,
it[realPos.fi].get(1, 0, (int)a[realPos.fi].size() - 1, 0, realPos.se) ) + 1 << '\n';
}
else {
int e; cin >> e;
int ran = 10;
for (int i = 10; i > e; --i) if (pos[i] == realPos) ran = i;
for (int i = ran; i > e; --i) pos[i] = pos[i - 1];
pos[e] = realPos;
for (int i = e; i > 0; --i) {
++cur;
if (pos[i].fi == -1) continue ;
it[ pos[i].fi ].update(1, 0, (int)a[ pos[i].fi ].size() - 1, pos[i].se, cur);
}
}
}
return 0;
}
Compilation message
cake.cpp: In member function 'void It::build_tree(bool, int, int, int)':
cake.cpp:22:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = Left + Right >> 1;
~~~~~^~~~~~~
cake.cpp: In member function 'void It::update(int, int, int, int, int)':
cake.cpp:29:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = Left + Right >> 1;
~~~~~^~~~~~~
cake.cpp: In member function 'int It::get(int, int, int, int, int)':
cake.cpp:37:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = Left + Right >> 1;
~~~~~^~~~~~~
cake.cpp: In member function 'int It::getPos(int, int, int, int)':
cake.cpp:42:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = Left + Right >> 1;
~~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
408 KB |
Output is correct |
| 4 |
Correct |
4 ms |
616 KB |
Output is correct |
| 5 |
Correct |
7 ms |
1072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
215 ms |
1072 KB |
Output is correct |
| 2 |
Correct |
108 ms |
1072 KB |
Output is correct |
| 3 |
Correct |
165 ms |
1072 KB |
Output is correct |
| 4 |
Correct |
102 ms |
1072 KB |
Output is correct |
| 5 |
Correct |
225 ms |
1180 KB |
Output is correct |
| 6 |
Correct |
170 ms |
1232 KB |
Output is correct |
| 7 |
Correct |
182 ms |
1232 KB |
Output is correct |
| 8 |
Correct |
110 ms |
1232 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
2940 KB |
Output is correct |
| 2 |
Correct |
45 ms |
2940 KB |
Output is correct |
| 3 |
Correct |
41 ms |
2940 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2940 KB |
Output is correct |
| 5 |
Correct |
72 ms |
4636 KB |
Output is correct |
| 6 |
Correct |
66 ms |
4668 KB |
Output is correct |
| 7 |
Correct |
56 ms |
4668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
4668 KB |
Output is correct |
| 2 |
Correct |
21 ms |
4668 KB |
Output is correct |
| 3 |
Correct |
40 ms |
4668 KB |
Output is correct |
| 4 |
Correct |
50 ms |
4668 KB |
Output is correct |
| 5 |
Correct |
67 ms |
4668 KB |
Output is correct |
| 6 |
Correct |
76 ms |
4668 KB |
Output is correct |
| 7 |
Correct |
79 ms |
4668 KB |
Output is correct |
| 8 |
Correct |
94 ms |
4668 KB |
Output is correct |
| 9 |
Correct |
370 ms |
5596 KB |
Output is correct |
| 10 |
Correct |
219 ms |
5596 KB |
Output is correct |
| 11 |
Correct |
269 ms |
5596 KB |
Output is correct |
| 12 |
Correct |
356 ms |
5596 KB |
Output is correct |
| 13 |
Correct |
293 ms |
6728 KB |
Output is correct |
