oj.uz

Submission #978373

# Submission time Handle Problem Language Result Execution time Memory
978373 2024-05-09T07:24:25 Z sleepntsheep Fish 3 (JOI24_fish3) C++17
9 / 100
 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

Main.cpp: In function 'int main()':
Main.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d%lld",&n,&d);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%lld",c+i),pc[i]=pc[i-1]+c[i];
      |         ~~~~~^~~~~~~~~~~~
Main.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
Main.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf("%d%d",&l,&r);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# 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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2069 ms 12896 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2016 ms 7788 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2009 ms 12164 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 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 -