| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 164560 |
2019-11-21T13:38:24 Z |
mhy908 |
Cake (CEOI14_cake) |
C++14 |
|
299 ms |
52984 KB |
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=9000000000000000000;
const int inf=2000000000;
struct SEGMENT_TREE
{
LL initial=-llinf;
int x=-1;
struct NODE{
int st, fin;
LL q;
}tree[1000000];
LL f(LL a, LL b){return max(a, b);}
void init(int point, int num){
if(num==1)tree[point].st=tree[point].fin=++x;
if(num<=1)return;
init(point*2, num-num/2);
init(point*2+1, num/2);
tree[point].st=tree[point*2].st;
tree[point].fin=tree[point*2+1].fin;
}
void update(int point, int num, LL qu){
if(tree[point].st==tree[point].fin){
tree[point].q=qu;
return;
}
if(num<=tree[point*2].fin)update(point*2, num, qu);
else update(point*2+1, num, qu);
tree[point].q=f(tree[point*2].q, tree[point*2+1].q);
}
LL max_query(int point, int a, int b){
if(tree[point].st>=a&&tree[point].fin<=b)return tree[point].q;
if(tree[point].st>b||tree[point].fin<a)return initial;
return f(max_query(point*2, a, b), max_query(point*2+1, a, b));
}
int find_query1(int point, int a, int b, LL num){
if(tree[point].st==tree[point].fin)return tree[point].st;
if(tree[point*2].fin<a)return find_query1(point*2+1, a, b, num);
if(tree[point*2+1].st>b)return find_query1(point*2, a, b, num);
if(max_query(point*2, a, tree[point*2].fin)>=num)return find_query1(point*2, a, b, num);
return find_query1(point*2+1, a, b, num);
}
int find_query2(int point, int a, int b, LL num){
if(tree[point].st==tree[point].fin)return tree[point].st;
if(tree[point*2].fin<a)return find_query2(point*2+1, a, b, num);
if(tree[point*2+1].st>b)return find_query2(point*2, a, b, num);
if(max_query(point*2+1, tree[point*2+1].st, b)>=num)return find_query2(point*2+1, a, b, num);
return find_query2(point*2, a, b, num);
}
void init(int num){init(1, num);}
void update(int num, LL qu){update(1, num, qu);}
LL max_query(int a, int b){return max_query(1, a, b);}
int find_query1(int a, int b, LL num){return find_query1(1, a, b, num);}
int find_query2(int a, int b, LL num){return find_query2(1, a, b, num);}
}seg;
set<pair<LL, int> > se;
int n, q, s, re1, re2;
LL d[250010];
int main()
{
scanf("%d %d", &n, &s);
seg.init(n+2);
for(int i=1; i<=n; i++){
scanf("%lld", &d[i]);
se.insert(mp(d[i], i));
if(i==s)continue;
seg.update(i, d[i]);
}
scanf("%d", &q);
seg.update(0, llinf);
seg.update(n+1, llinf);
for(int u=1; u<=q; u++){
char c;
scanf(" %c", &c);
if(c=='F'){
int temp;
scanf("%d", &temp);
if(temp==s){
puts("0");
continue;
}
if(s>temp){
LL tmp=seg.max_query(temp, s-1);
int ans=seg.find_query1(s+1, n+1, tmp);
printf("%d\n", ans-temp-1);
}
else{
LL tmp=seg.max_query(s+1, temp);
int ans=seg.find_query2(0, s-1, tmp);
printf("%d\n", temp-ans-1);
}
}
else{
int a, b;
scanf("%d %d", &a, &b);
auto it=se.find(mp(a, d[a])), it2=se.end();
it2--;
se.erase(it);
vector<int> p;
for(int i=1; i<=b; i++){
if(i==b){
d[a]=it2->F+1;
se.insert(mp(d[a], a));
seg.update(a, d[a]);
}
else{
p.pb(it2->S);
}
it2--;
}
for(int i=0; i<b-1; i++){
se.erase(mp(p[i], d[p[i]]));
d[p[i]]++;
se.insert(mp(p[i], d[p[i]]));
seg.update(p[i], d[p[i]]);
}
}
}
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &s);
~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &d[i]);
~~~~~^~~~~~~~~~~~~~~
cake.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
cake.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c", &c);
~~~~~^~~~~~~~~~~
cake.cpp:85:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &temp);
~~~~~^~~~~~~~~~~~~
cake.cpp:103:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
2936 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
12 ms |
3192 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
13 ms |
3064 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
10 ms |
2936 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
25 ms |
6264 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
19 ms |
6008 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
26 ms |
6264 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
19 ms |
6136 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
103 ms |
23160 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
78 ms |
23160 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
78 ms |
23288 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
6 ms |
760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
299 ms |
52976 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
297 ms |
52900 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
193 ms |
52984 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
1272 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
9 ms |
1784 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
45 ms |
11768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
39 ms |
11980 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
7 ms |
1144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
61 ms |
14300 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
13 ms |
3192 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
102 ms |
23288 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
297 ms |
52768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
5 ms |
888 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
43 ms |
5624 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
235 ms |
45816 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
288 ms |
52984 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
