| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 52506 |
2018-06-26T06:19:17 Z |
zadrga |
Cake (CEOI14_cake) |
C++14 |
|
1742 ms |
103072 KB |
//7.57
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define INF (2e9)
#define maxn 250111
typedef long long ll;
typedef pair<int, int> pii;
set<pii> s;
int val[maxn], seg[4 * maxn];
int n, a;
struct segtree_right{
int seg[4 * maxn];
void update(int x, int l, int d, int i, int y){
if(l > d || l > i || d < i)
return;
if(l == d && l == i){
seg[x] = y;
return;
}
int mid = (l + d) / 2;
update(2 * x, l, mid, i, y);
update(2 * x + 1, mid + 1, d, i, y);
seg[x] = max(seg[2 * x], seg[2 * x + 1]);
}
int find_max(int x, int l, int d, int i, int j){
if(l > d || l > j || d < i)
return -1;
if(i <= l && d <= j)
return seg[x];
int mid = (l + d) / 2;
int ret = find_max(2 * x, l, mid, i, j);
ret = max(ret, find_max(2 * x + 1, mid + 1, d, i, j));
return ret;
}
int query(int x, int l, int d, int y){
if(l > d)
return -1;
if(l == d){
if(seg[x] <= y)
return d + 1;
else
return d;
}
int mid = (l + d) / 2;
if(seg[2 * x] <= y)
return query(2 * x + 1, mid + 1, d, y);
if(seg[2 * x] > y)
return query(2 * x, l, mid, y);
}
} seg_right;
struct segtree_left{
int seg[4 * maxn];
void update(int x, int l, int d, int i, int y){
if(l > d || l > i || d < i)
return;
if(l == d && l == i){
seg[x] = y;
return;
}
int mid = (l + d) / 2;
update(2 * x, l, mid, i, y);
update(2 * x + 1, mid + 1, d, i, y);
seg[x] = max(seg[2 * x], seg[2 * x + 1]);
}
int find_max(int x, int l, int d, int i, int j){
if(l > d || l > j || d < i)
return -1;
if(i <= l && d <= j)
return seg[x];
int mid = (l + d) / 2;
int ret = find_max(2 * x, l, mid, i, j);
ret = max(ret, find_max(2 * x + 1, mid + 1, d, i, j));
return ret;
}
int query(int x, int l, int d, int y){
if(l > d)
return -1;
if(l == d){
if(seg[x] <= y)
return d + 1;
else
return d;
}
int mid = (l + d) / 2;
if(seg[2 * x + 1] <= y)
return query(2 * x, l, mid, y);
if(seg[2 * x + 1] > y)
return query(2 * x + 1, mid + 1, d, y);
}
} seg_left;
int find_ans(int x){
if(x < a){
int maks = seg_left.find_max(1, 1, a - 1, x, a - 1);
int pos = seg_right.query(1, a + 1, n, maks);
int ret = pos - a + (a - x) - 1;
return ret;
}
if(x > a){
int maks = seg_right.find_max(1, a + 1, n, a + 1, x);
int pos = seg_left.query(1, 1, a - 1, maks);
int ret = a - pos + (x - a) - 1;
return ret;
}
}
void change(int x, int y){
s.erase(mp(val[x], x));
val[x] = y;
s.insert(mp(val[x], x));
if(x < a)
seg_left.update(1, 1, a - 1, x, val[x]);
if(x > a)
seg_right.update(1, a + 1, n, x, val[x]);
}
int main(){
scanf("%d%d", &n, &a);
for(int i = 1; i <= n; i++){
scanf("%d", val + i);
s.insert(mp(val[i], i));
if(i < a)
seg_left.update(1, 1, a - 1, i, val[i]);
if(i > a)
seg_right.update(1, a + 1, n, i, val[i]);
}
int q;
scanf("%d", &q);
while(q--){
char t[2];
int x, y;
scanf("%s%d", t, &x);
if(t[0] == 'F'){
if(x == a){
printf("0\n");
continue;
}
printf("%d\n", find_ans(x));
}
if(t[0] == 'E'){
scanf("%d", &y);
if(x == a)
continue;
auto it = s.end();
vector<int> cur;
for(int i = 0; i < y - 1; i++){
it--;
cur.pb(it -> se);
}
it--;
change(x, val[it -> se] + 1);
for(int i : cur)
change(i, val[i] + 1);
}
}
return 0;
}
Compilation message
cake.cpp: In function 'int find_ans(int)':
cake.cpp:136:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
cake.cpp: In member function 'int segtree_right::query(int, int, int, int)':
cake.cpp:68:2: warning: control reaches end of non-void function [-Wreturn-type]
}
^
cake.cpp: In member function 'int segtree_left::query(int, int, int, int)':
cake.cpp:119:2: warning: control reaches end of non-void function [-Wreturn-type]
}
^
cake.cpp: In function 'int main()':
cake.cpp:150:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &a);
~~~~~^~~~~~~~~~~~~~~~
cake.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", val + i);
~~~~~^~~~~~~~~~~~~~~
cake.cpp:162:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
cake.cpp:166:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s%d", t, &x);
~~~~~^~~~~~~~~~~~~~~
cake.cpp:178:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &y);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
952 ms |
5564 KB |
Output is correct |
| 2 |
Incorrect |
454 ms |
10152 KB |
Output isn't correct |
| 3 |
Correct |
563 ms |
14684 KB |
Output is correct |
| 4 |
Incorrect |
279 ms |
19072 KB |
Output isn't correct |
| 5 |
Correct |
1014 ms |
24724 KB |
Output is correct |
| 6 |
Incorrect |
775 ms |
29820 KB |
Output isn't correct |
| 7 |
Correct |
710 ms |
34580 KB |
Output is correct |
| 8 |
Incorrect |
366 ms |
39572 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
46124 KB |
Output is correct |
| 2 |
Incorrect |
119 ms |
47432 KB |
Output isn't correct |
| 3 |
Incorrect |
109 ms |
48792 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
48792 KB |
Output isn't correct |
| 5 |
Incorrect |
388 ms |
60136 KB |
Output isn't correct |
| 6 |
Correct |
359 ms |
62796 KB |
Output is correct |
| 7 |
Incorrect |
209 ms |
64744 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
64744 KB |
Output isn't correct |
| 2 |
Incorrect |
56 ms |
64744 KB |
Output isn't correct |
| 3 |
Incorrect |
142 ms |
64744 KB |
Output isn't correct |
| 4 |
Incorrect |
193 ms |
64744 KB |
Output isn't correct |
| 5 |
Incorrect |
279 ms |
64744 KB |
Output isn't correct |
| 6 |
Correct |
270 ms |
64744 KB |
Output is correct |
| 7 |
Correct |
240 ms |
64744 KB |
Output is correct |
| 8 |
Incorrect |
487 ms |
65440 KB |
Output isn't correct |
| 9 |
Incorrect |
1741 ms |
82032 KB |
Output isn't correct |
| 10 |
Incorrect |
780 ms |
82032 KB |
Output isn't correct |
| 11 |
Correct |
1134 ms |
82032 KB |
Output is correct |
| 12 |
Correct |
1742 ms |
93348 KB |
Output is correct |
| 13 |
Incorrect |
1280 ms |
103072 KB |
Output isn't correct |
