# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
171504 |
2019-12-28T21:30:03 Z |
TadijaSebez |
Cake (CEOI14_cake) |
C++11 |
|
2000 ms |
25788 KB |
#include <bits/stdc++.h>
using namespace std;
const int N=250050;
const int M=2*N;
int ls[M],rs[M],tsz,root,mx[M];
void Set(int &c, int ss, int se, int qi, int val)
{
if(!c) c=++tsz;
if(ss==se){ mx[c]=val;return;}
int mid=ss+se>>1;
if(qi<=mid) Set(ls[c],ss,mid,qi,val);
else Set(rs[c],mid+1,se,qi,val);
mx[c]=max(mx[ls[c]],mx[rs[c]]);
}
int Get(int c, int ss, int se, int qs, int qe)
{
if(qs>qe || qs>se || ss>qe) return 0;
if(qs<=ss && qe>=se) return mx[c];
int mid=ss+se>>1;
return max(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe));
}
set<pair<int,int>> ord;
int d[N];
int main()
{
int n,q,a;
scanf("%i %i",&n,&a);
for(int i=1;i<=n;i++)
{
scanf("%i",&d[i]);
Set(root,1,n,i,d[i]);
ord.insert({d[i],i});
}
scanf("%i",&q);
while(q--)
{
char t;
scanf("\n%c",&t);
if(t=='F')
{
int b;
scanf("%i",&b);
if(b==a) printf("0\n");
else if(b>a)
{
int val=Get(root,1,n,a+1,b);
int top=a-1,bot=1,mid,ans=a;
while(top>=bot)
{
mid=top+bot>>1;
if(Get(root,1,n,mid,a-1)<val) top=mid-1,ans=mid;
else bot=mid+1;
}
printf("%i\n",b-ans);
}
else
{
int val=Get(root,1,n,b,a-1);
int top=n,bot=a+1,mid,ans=a;
while(top>=bot)
{
mid=top+bot>>1;
if(Get(root,1,n,a+1,mid)<val) bot=mid+1,ans=mid;
else top=mid-1;
}
printf("%i\n",ans-b);
}
}
else
{
int b,e;
scanf("%i %i",&b,&e);
stack<pair<int,int>> bck;
ord.erase({d[b],b});
while(--e)
{
pair<int,int> top=*ord.rbegin();
ord.erase(--ord.end());
top.first++;
d[top.second]++;
Set(root,1,n,top.second,top.first);
bck.push(top);
}
int my=1;
if(ord.size()) my=ord.rbegin()->first+1;
Set(root,1,n,b,my);
d[b]=my;
ord.insert({d[b],b});
while(bck.size())
{
pair<int,int> top=bck.top();
bck.pop();
Set(root,1,n,top.second,top.first);
ord.insert(top);
}
}
}
return 0;
}
Compilation message
cake.cpp: In function 'void Set(int&, int, int, int, int)':
cake.cpp:10:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
cake.cpp: In function 'int Get(int, int, int, int, int)':
cake.cpp:19:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
cake.cpp: In function 'int main()':
cake.cpp:50:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mid=top+bot>>1;
~~~^~~~
cake.cpp:62:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mid=top+bot>>1;
~~~^~~~
cake.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i",&n,&a);
~~~~~^~~~~~~~~~~~~~~
cake.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&d[i]);
~~~~~^~~~~~~~~~~~
cake.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&q);
~~~~~^~~~~~~~~
cake.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("\n%c",&t);
~~~~~^~~~~~~~~~~
cake.cpp:42:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&b);
~~~~~^~~~~~~~~
cake.cpp:72:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i",&b,&e);
~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
12 ms |
504 KB |
Output is correct |
5 |
Correct |
39 ms |
1272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
862 ms |
5428 KB |
Output is correct |
2 |
Correct |
523 ms |
5624 KB |
Output is correct |
3 |
Correct |
622 ms |
5640 KB |
Output is correct |
4 |
Correct |
348 ms |
5500 KB |
Output is correct |
5 |
Correct |
1076 ms |
6888 KB |
Output is correct |
6 |
Correct |
835 ms |
7436 KB |
Output is correct |
7 |
Correct |
720 ms |
7176 KB |
Output is correct |
8 |
Correct |
442 ms |
7404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
607 ms |
9916 KB |
Output is correct |
2 |
Correct |
416 ms |
9888 KB |
Output is correct |
3 |
Correct |
408 ms |
9720 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
733 ms |
22260 KB |
Output is correct |
6 |
Correct |
883 ms |
22188 KB |
Output is correct |
7 |
Correct |
634 ms |
21928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
121 ms |
1144 KB |
Output is correct |
2 |
Correct |
106 ms |
1244 KB |
Output is correct |
3 |
Correct |
304 ms |
5356 KB |
Output is correct |
4 |
Correct |
331 ms |
5216 KB |
Output is correct |
5 |
Correct |
292 ms |
1912 KB |
Output is correct |
6 |
Correct |
621 ms |
7544 KB |
Output is correct |
7 |
Correct |
396 ms |
3484 KB |
Output is correct |
8 |
Correct |
479 ms |
10396 KB |
Output is correct |
9 |
Execution timed out |
2043 ms |
25188 KB |
Time limit exceeded |
10 |
Correct |
968 ms |
5336 KB |
Output is correct |
11 |
Correct |
1467 ms |
7556 KB |
Output is correct |
12 |
Execution timed out |
2066 ms |
21320 KB |
Time limit exceeded |
13 |
Execution timed out |
2065 ms |
25788 KB |
Time limit exceeded |