# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
38615 |
2018-01-05T04:35:15 Z |
sinhriv |
Cake (CEOI14_cake) |
C++14 |
|
989 ms |
17312 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 250020;
int n, p;
int a[N];
int mark[N];
#define mid ((l + r) >> 1)
int tree[N << 2];
int lazy[N << 3];
void build(int x, int l, int r){
if(l == r){
tree[x] = a[r];
return;
}
build(x + x, l, mid);
build(x + x + 1, mid + 1, r);
tree[x] = max(tree[x + x], tree[x + x + 1]);
}
int finLeft(int x, int l, int r, int u, int v, int val){
if(u > v) return 0;
if(l > v || r < u) return 0;
if(tree[x] <= val) return 0;
if(l >= u && r <= v){
if(l == r) {
return r;
}
if(tree[x + x + 1] > val) return finLeft(x + x + 1, mid + 1, r, u, v, val);
return finLeft(x + x, l, mid, u, v, val);
}
int ret = finLeft(x + x + 1, mid + 1, r, u, v, val);
if(ret != 0) return ret;
return finLeft(x + x, l, mid, u, v, val);
}
int finRight(int x, int l, int r, int u, int v, int val){
if(u > v) return n + 1;
if(l > v || r < u) return n + 1;
if(tree[x] <= val) return n + 1;
if(l >= u && r <= v){
if(l == r) return r;
if(tree[x + x] > val) return finRight(x + x, l, mid, u, v, val);
return finRight(x + x + 1, mid + 1, r, u, v, val);
}
int ret = finRight(x + x, l, mid, u, v, val);
if(ret != n + 1) return ret;
return finRight(x + x + 1, mid + 1, r, u, v, val);
}
void modify(int x, int l, int r, int pos, int val){
if(l > pos || r < pos) return;
if(l == r) {
tree[x] = val;
return;
}
modify(x + x, l, mid, pos, val);
modify(x + x + 1, mid + 1, r, pos, val);
tree[x] = max(tree[x + x], tree[x + x + 1]);
}
int query(int x, int l, int r, int u, int v){
if(u > v) return 0;
if(l > v || r < u) return 0;
if(l >= u && r <= v) return tree[x];
return max(query(x + x, l, mid, u, v), query(x + x + 1, mid + 1, r, u, v));
}
bool cmp(int x, int y){
return a[x] > a[y];
}
int main(){
if(fopen("1.inp", "r")){
freopen("1.inp", "r", stdin);
}
vector < int > perm;
scanf("%d%d", &n, &p);
for(int i = 1; i <= n; ++i){
scanf("%d", a + i);
perm.push_back(i);
}
build(1, 1, n);
memset(mark, -1, sizeof mark);
sort(perm.begin(), perm.end(), cmp);
perm.resize(min(n, 10));
for(int i = 0; i < perm.size(); ++i){
mark[perm[i]] = i;
}
int q;
scanf("%d", &q);
int curr = n;
while(q--){
char read[5];
scanf("%s", read);
if(read[0] == 'F'){
int x;
scanf("%d", &x);
if(x == p) puts("0");
else{
if(x < p){
printf("%d\n", finRight(1, 1, n, p + 1, n, query(1, 1, n, x, p - 1)) - x - 1);
}
else{
printf("%d\n", x - finLeft(1, 1, n, 1, p - 1, query(1, 1, n, p + 1, x)) - 1);
}
}
}
else{
int x, t;
scanf("%d%d", &x, &t);
int save = mark[x];
for(int x : perm) mark[x] = -1;
for(int i = (save != -1 ? save : perm.size() - 1); i >= t; --i){
perm[i] = perm[i - 1];
}
perm[t - 1] = x;
curr += 11;
for(int i = 0; i < perm.size(); ++i){
mark[perm[i]] = i;
modify(1, 1, n, perm[i], curr - i);
}
}
}
return 0;
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:112:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < perm.size(); ++i){
^
cake.cpp:155:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < perm.size(); ++i){
^
cake.cpp:91:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("1.inp", "r", stdin);
^
cake.cpp:96:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &p);
^
cake.cpp:98:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", a + i);
^
cake.cpp:117:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
^
cake.cpp:123:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", read);
^
cake.cpp:127:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
^
cake.cpp:141:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &t);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
15692 KB |
Output is correct |
2 |
Correct |
0 ms |
15692 KB |
Output is correct |
3 |
Correct |
0 ms |
15692 KB |
Output is correct |
4 |
Correct |
6 ms |
15692 KB |
Output is correct |
5 |
Correct |
16 ms |
15832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
756 ms |
15832 KB |
Output is correct |
2 |
Correct |
779 ms |
15832 KB |
Output is correct |
3 |
Correct |
813 ms |
15832 KB |
Output is correct |
4 |
Correct |
706 ms |
15832 KB |
Output is correct |
5 |
Correct |
839 ms |
15964 KB |
Output is correct |
6 |
Correct |
896 ms |
15964 KB |
Output is correct |
7 |
Correct |
916 ms |
15964 KB |
Output is correct |
8 |
Correct |
779 ms |
15964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
166 ms |
16544 KB |
Output is correct |
2 |
Correct |
109 ms |
16544 KB |
Output is correct |
3 |
Correct |
113 ms |
16544 KB |
Output is correct |
4 |
Correct |
0 ms |
15692 KB |
Output is correct |
5 |
Correct |
169 ms |
17312 KB |
Output is correct |
6 |
Correct |
186 ms |
17312 KB |
Output is correct |
7 |
Correct |
183 ms |
17312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
15692 KB |
Output is correct |
2 |
Correct |
53 ms |
15832 KB |
Output is correct |
3 |
Correct |
113 ms |
16160 KB |
Output is correct |
4 |
Correct |
126 ms |
16160 KB |
Output is correct |
5 |
Correct |
149 ms |
15692 KB |
Output is correct |
6 |
Correct |
236 ms |
16544 KB |
Output is correct |
7 |
Correct |
226 ms |
15832 KB |
Output is correct |
8 |
Correct |
436 ms |
16544 KB |
Output is correct |
9 |
Correct |
986 ms |
17312 KB |
Output is correct |
10 |
Correct |
519 ms |
15692 KB |
Output is correct |
11 |
Correct |
649 ms |
15964 KB |
Output is correct |
12 |
Correct |
989 ms |
17312 KB |
Output is correct |
13 |
Correct |
843 ms |
17312 KB |
Output is correct |