| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 171509 |
2019-12-28T21:37:11 Z |
TadijaSebez |
Cake (CEOI14_cake) |
C++11 |
|
2000 ms |
18148 KB |
#include <bits/stdc++.h>
using namespace std;
#define ls c<<1
#define rs c<<1|1
const int N=250050;
const int M=4*N;
int root=1,mx[M];
int d[N];
int cmb(int i, int j){ return d[i]>d[j]?i:j;}
void Set(int c, int ss, int se, int qi)
{
if(ss==se){ mx[c]=qi;return;}
int mid=ss+se>>1;
if(qi<=mid) Set(ls,ss,mid,qi);
else Set(rs,mid+1,se,qi);
mx[c]=cmb(mx[ls],mx[rs]);
}
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 cmb(Get(ls,ss,mid,qs,qe),Get(rs,mid+1,se,qs,qe));
}
set<pair<int,int>> ord;
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);
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=d[Get(root,1,n,a+1,b)];
int top=a-1,bot=1,mid,ans=a;
while(top>=bot)
{
mid=top+bot>>1;
if(d[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=d[Get(root,1,n,b,a-1)];
int top=n,bot=a+1,mid,ans=a;
while(top>=bot)
{
mid=top+bot>>1;
if(d[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]++;
bck.push(top);
}
int my=1;
if(ord.size()) my=ord.rbegin()->first+1;
Set(root,1,n,b);
d[b]=my;
ord.insert({d[b],b});
while(bck.size())
{
pair<int,int> top=bck.top();
bck.pop();
ord.insert(top);
}
}
}
return 0;
}
Compilation message
cake.cpp: In function 'void Set(int, int, int, int)':
cake.cpp:13: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:22:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
cake.cpp: In function 'int main()':
cake.cpp:52:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mid=top+bot>>1;
~~~^~~~
cake.cpp:64:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mid=top+bot>>1;
~~~^~~~
cake.cpp:29: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:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&d[i]);
~~~~~^~~~~~~~~~~~
cake.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&q);
~~~~~^~~~~~~~~
cake.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("\n%c",&t);
~~~~~^~~~~~~~~~~
cake.cpp:44:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&b);
~~~~~^~~~~~~~~
cake.cpp:74: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 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
552 ms |
1176 KB |
Output isn't correct |
| 2 |
Incorrect |
417 ms |
1240 KB |
Output isn't correct |
| 3 |
Incorrect |
473 ms |
1232 KB |
Output isn't correct |
| 4 |
Correct |
348 ms |
1236 KB |
Output is correct |
| 5 |
Incorrect |
670 ms |
2100 KB |
Output isn't correct |
| 6 |
Incorrect |
587 ms |
2128 KB |
Output isn't correct |
| 7 |
Incorrect |
532 ms |
2120 KB |
Output isn't correct |
| 8 |
Correct |
422 ms |
2124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
590 ms |
7224 KB |
Output isn't correct |
| 2 |
Incorrect |
394 ms |
7176 KB |
Output isn't correct |
| 3 |
Incorrect |
421 ms |
7148 KB |
Output isn't correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Incorrect |
709 ms |
15984 KB |
Output isn't correct |
| 6 |
Incorrect |
870 ms |
15960 KB |
Output isn't correct |
| 7 |
Correct |
629 ms |
15788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
892 KB |
Output isn't correct |
| 2 |
Incorrect |
99 ms |
940 KB |
Output isn't correct |
| 3 |
Incorrect |
274 ms |
3844 KB |
Output isn't correct |
| 4 |
Incorrect |
238 ms |
3872 KB |
Output isn't correct |
| 5 |
Incorrect |
224 ms |
988 KB |
Output isn't correct |
| 6 |
Incorrect |
518 ms |
4852 KB |
Output isn't correct |
| 7 |
Incorrect |
345 ms |
1668 KB |
Output isn't correct |
| 8 |
Incorrect |
370 ms |
6716 KB |
Output isn't correct |
| 9 |
Execution timed out |
2032 ms |
18148 KB |
Time limit exceeded |
| 10 |
Incorrect |
739 ms |
1924 KB |
Output isn't correct |
| 11 |
Incorrect |
1081 ms |
3304 KB |
Output isn't correct |
| 12 |
Execution timed out |
2003 ms |
15736 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2033 ms |
17936 KB |
Time limit exceeded |
