# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
978373 | 2024-05-09T07:24:25 Z | sleepntsheep | Fish 3 (JOI24_fish3) | C++17 | 2000 ms | 12896 KB |
long long lo(long long a,long long b){return a<b?a:b;} long long hi(long long a,long long b){return a>b?a:b;} #include<stdio.h> #include<assert.h> #include<string.h> #define N 300005 int n,q; long long d,c[N],t[N],b[N],pc[N],bo,suff_min[N]; int main() { scanf("%d%lld",&n,&d); for(int i=1;i<=n;++i) { scanf("%lld",c+i),pc[i]=pc[i-1]+c[i]; if(!c[i])b[bo++]=i; } scanf("%d",&q); for(int l,r,i=0;i<q;++i) { scanf("%d%d",&l,&r); memcpy(t,c,sizeof t); long long run=0,z=0; for(int i=l;i<=r;++i) { if(t[i]<run) { puts("-1"); goto X; } run+=(t[i]-run)%d; t[i]-=run; } suff_min[r]=t[r]; for(int i=r-1;i>=l;--i)suff_min[i]=lo(suff_min[i+1],t[i]); run=0; for(int i=l;i<=r;++i) { if(suff_min[i]-run>=d) { for(int j=i;j<=r;++j) t[i]-=(suff_min[i]-run)/d*d; run+=(suff_min[i]-run)/d*d; } } for(int i=l;i<=r;++i) { if(t[i]%d){puts("-1");goto X;} z+=t[i]/d; } printf("%lld\n",z); X:; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 6492 KB | Output is correct |
2 | Correct | 1 ms | 6492 KB | Output is correct |
3 | Correct | 1 ms | 6492 KB | Output is correct |
4 | Correct | 284 ms | 6700 KB | Output is correct |
5 | Correct | 224 ms | 6680 KB | Output is correct |
6 | Correct | 261 ms | 6664 KB | Output is correct |
7 | Correct | 223 ms | 6648 KB | Output is correct |
8 | Correct | 227 ms | 8696 KB | Output is correct |
9 | Correct | 220 ms | 8684 KB | Output is correct |
10 | Correct | 302 ms | 6692 KB | Output is correct |
11 | Correct | 219 ms | 6740 KB | Output is correct |
12 | Correct | 319 ms | 6500 KB | Output is correct |
13 | Correct | 259 ms | 6740 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2069 ms | 12896 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2016 ms | 7788 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2009 ms | 12164 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 6492 KB | Output is correct |
2 | Correct | 1 ms | 6492 KB | Output is correct |
3 | Correct | 1 ms | 6492 KB | Output is correct |
4 | Correct | 284 ms | 6700 KB | Output is correct |
5 | Correct | 224 ms | 6680 KB | Output is correct |
6 | Correct | 261 ms | 6664 KB | Output is correct |
7 | Correct | 223 ms | 6648 KB | Output is correct |
8 | Correct | 227 ms | 8696 KB | Output is correct |
9 | Correct | 220 ms | 8684 KB | Output is correct |
10 | Correct | 302 ms | 6692 KB | Output is correct |
11 | Correct | 219 ms | 6740 KB | Output is correct |
12 | Correct | 319 ms | 6500 KB | Output is correct |
13 | Correct | 259 ms | 6740 KB | Output is correct |
14 | Execution timed out | 2069 ms | 12896 KB | Time limit exceeded |
15 | Halted | 0 ms | 0 KB | - |