| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 38612 |
2018-01-05T04:21:06 Z |
sinhriv |
Cake (CEOI14_cake) |
C++14 |
|
1016 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);
perm.resize(min(n, 10));
memset(mark, -1, sizeof mark);
sort(perm.begin(), perm.end(), cmp);
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);
for(int i = (mark[x] != -1 ? mark[x] : 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){
modify(1, 1, n, perm[i], curr - i);
}
}
}
return 0;
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:111:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < perm.size(); ++i){
^
cake.cpp:151: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:116:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
^
cake.cpp:122:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", read);
^
cake.cpp:126:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
^
cake.cpp:140: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 |
Incorrect |
0 ms |
15692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
829 ms |
15832 KB |
Output isn't correct |
| 2 |
Incorrect |
686 ms |
15832 KB |
Output isn't correct |
| 3 |
Incorrect |
703 ms |
15832 KB |
Output isn't correct |
| 4 |
Correct |
849 ms |
15832 KB |
Output is correct |
| 5 |
Incorrect |
876 ms |
15964 KB |
Output isn't correct |
| 6 |
Incorrect |
796 ms |
15964 KB |
Output isn't correct |
| 7 |
Incorrect |
803 ms |
15964 KB |
Output isn't correct |
| 8 |
Correct |
843 ms |
15964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
119 ms |
16544 KB |
Output isn't correct |
| 2 |
Incorrect |
99 ms |
16544 KB |
Output isn't correct |
| 3 |
Incorrect |
73 ms |
16544 KB |
Output isn't correct |
| 4 |
Incorrect |
0 ms |
15692 KB |
Output isn't correct |
| 5 |
Incorrect |
146 ms |
17312 KB |
Output isn't correct |
| 6 |
Incorrect |
136 ms |
17312 KB |
Output isn't correct |
| 7 |
Incorrect |
109 ms |
17312 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
15692 KB |
Output isn't correct |
| 2 |
Incorrect |
63 ms |
15832 KB |
Output isn't correct |
| 3 |
Incorrect |
133 ms |
16160 KB |
Output isn't correct |
| 4 |
Incorrect |
126 ms |
16160 KB |
Output isn't correct |
| 5 |
Incorrect |
163 ms |
15692 KB |
Output isn't correct |
| 6 |
Incorrect |
243 ms |
16544 KB |
Output isn't correct |
| 7 |
Incorrect |
259 ms |
15832 KB |
Output isn't correct |
| 8 |
Incorrect |
389 ms |
16544 KB |
Output isn't correct |
| 9 |
Incorrect |
1016 ms |
17312 KB |
Output isn't correct |
| 10 |
Incorrect |
526 ms |
15692 KB |
Output isn't correct |
| 11 |
Incorrect |
669 ms |
15964 KB |
Output isn't correct |
| 12 |
Incorrect |
949 ms |
17312 KB |
Output isn't correct |
| 13 |
Incorrect |
806 ms |
17312 KB |
Output isn't correct |
