| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 101477 |
2019-03-19T03:01:57 Z |
errorgorn |
Cake (CEOI14_cake) |
C++14 |
|
2000 ms |
5344 KB |
#include <cstdio>
#include <vector>
#include <utility>
#include <deque>
using namespace std;
typedef pair<int,int> ii;
int n,d,q;
int E,F;
int arr[250005],top[12];
int memo[250005];
ii query[500005];
void print(){
for (int x=0;x<n;x++){
printf("%d ",arr[x]);
}
printf("\n");
for (int x=0;x<min(n,10);x++){
printf("%d ",top[x]);
}
printf("\n");
}
int f(int i){
if (d==i) return 0;
else{
int ans=1;
ii a=ii(1000000000,-1), b=ii(1000000000,-1);
if (d!=0) a=ii(arr[d-1],d-1);
if (d!=n-1) b=ii(arr[d+1],d+1);
if (a>b) swap(a,b);
while (a.second!=i){
//printf("%d %d\n",a.second,b.second);
if (a.second<d){
if (a.second!=0) a=ii(arr[a.second-1],a.second-1);
else a=ii(1000000000,-1);
}
else{
if (a.second!=n-1) a=ii(arr[a.second+1],a.second+1);
else a=ii(1000000000,-1);
}
if (a>b) swap(a,b);
ans++;
}
return ans;
}
}
void memof(){
memo[d]=0;
int ans=1;
ii a=ii(1000000000,-1), b=ii(1000000000,-1);
if (d!=0) a=ii(arr[d-1],d-1);
if (d!=n-1) b=ii(arr[d+1],d+1);
if (a>b) swap(a,b);
while (a.first!=1000000000){
memo[a.second]=ans++;
if (a.second<d){
if (a.second!=0) a=ii(arr[a.second-1],a.second-1);
else a=ii(1000000000,-1);
}
else{
if (a.second!=n-1) a=ii(arr[a.second+1],a.second+1);
else a=ii(1000000000,-1);
}
if (a>b) swap(a,b);
}
}
void print2(){
for (int x=0;x<n;x++){
printf("%d ",f(x));
}
printf("\n\n");
}
int main(){
//freopen("input.txt","r",stdin);
int a,b;
scanf("%d%d",&n,&d);
d--;
for (int x=0;x<n;x++){
scanf("%d",&arr[x]);
}
scanf("%d",&q);
for (int x=0;x<q;x++){
getchar();
if (getchar()=='E'){
scanf("%d%d",&a,&b);
query[x]=(ii(a-1,b-1));
E++;
}
else{
scanf("%d",&a);
query[x]=(ii(a-1,-1));
F++;
}
}
for (int x=0;x<n;x++){
if (arr[x]>n-10) top[n-arr[x]]=x;
}
int tb=min(n,10);
ii it;
//print();
if ( (n<=10000 && q<=10000) || F<=500){
for (int __x=0;__x<q;__x++){
it=query[__x];
if ((it).second==-1){ //this is F
printf("%d\n",f((it).first));
}
else{ //this is E
arr[(it).first]=arr[top[(it).second]]+1;
for (int x=0;x<(it).second;x++){
arr[top[x]]++;
}
int _x;
for (_x=(it).second;_x<n && top[_x]!=(it).first;_x++){}
for (int x=_x;x>(it).second;x--){
top[x]=top[x-1];
}
top[(it).second]=(it).first;
//print();
//print2();
}
}
}
else if (E<=100){
for (int __x=0;__x<q;__x++){
it=query[__x];
if ((it).second==-1){ //this is F
printf("%d\n",memo[(it).first]);
}
else{ //this is E
arr[(it).first]=arr[top[(it).second]]+1;
for (int x=0;x<(it).second;x++){
arr[top[x]]++;
}
int _x;
for (_x=(it).second;_x<n && top[_x]!=(it).first;_x++){}
for (int x=_x;x>(it).second;x--){
top[x]=top[x-1];
}
top[(it).second]=(it).first;
memof();
}
}
}
else{
printf("goodbye world\n");
}
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:97:9: warning: unused variable 'tb' [-Wunused-variable]
int tb=min(n,10);
^~
cake.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&d);
~~~~~^~~~~~~~~~~~~~
cake.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&arr[x]);
~~~~~^~~~~~~~~~~~~~
cake.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
~~~~~^~~~~~~~~
cake.cpp:84:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);
~~~~~^~~~~~~~~~~~~~
cake.cpp:89:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a);
~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1004 ms |
4308 KB |
Output isn't correct |
| 2 |
Incorrect |
177 ms |
4300 KB |
Output isn't correct |
| 3 |
Incorrect |
656 ms |
4188 KB |
Output isn't correct |
| 4 |
Correct |
99 ms |
4344 KB |
Output is correct |
| 5 |
Execution timed out |
2048 ms |
4344 KB |
Time limit exceeded |
| 6 |
Incorrect |
1342 ms |
4480 KB |
Output isn't correct |
| 7 |
Incorrect |
1541 ms |
4480 KB |
Output isn't correct |
| 8 |
Correct |
114 ms |
4344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
2472 KB |
Output isn't correct |
| 2 |
Incorrect |
59 ms |
2300 KB |
Output isn't correct |
| 3 |
Incorrect |
98 ms |
2296 KB |
Output isn't correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Incorrect |
113 ms |
3704 KB |
Output isn't correct |
| 6 |
Incorrect |
98 ms |
3676 KB |
Output isn't correct |
| 7 |
Incorrect |
78 ms |
3448 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
768 KB |
Output isn't correct |
| 2 |
Incorrect |
12 ms |
768 KB |
Output isn't correct |
| 3 |
Incorrect |
20 ms |
1152 KB |
Output isn't correct |
| 4 |
Incorrect |
20 ms |
1144 KB |
Output isn't correct |
| 5 |
Incorrect |
28 ms |
1500 KB |
Output isn't correct |
| 6 |
Incorrect |
56 ms |
1784 KB |
Output isn't correct |
| 7 |
Incorrect |
40 ms |
1912 KB |
Output isn't correct |
| 8 |
Incorrect |
95 ms |
2296 KB |
Output isn't correct |
| 9 |
Incorrect |
138 ms |
5344 KB |
Output isn't correct |
| 10 |
Incorrect |
118 ms |
4280 KB |
Output isn't correct |
| 11 |
Incorrect |
88 ms |
4316 KB |
Output isn't correct |
| 12 |
Incorrect |
126 ms |
4956 KB |
Output isn't correct |
| 13 |
Incorrect |
132 ms |
5308 KB |
Output isn't correct |
