oj.uz

Submission #1030918

# Submission time Handle Problem Language Result Execution time Memory
1030918 2024-07-22T12:08:05 Z sleepntsheep Addk (eJOI21_addk) C
92 / 100
 40 ms 6228 KB 
#include<stdio.h>
#define N 100000
#define N_ N+1
int lo(int i,int j){return i<j?i:j;}
int hi(int i,int j){return -lo(-i,-j);}
int n,k,q_,a[N_],a_,x,y,m;
long long p[N_],q[N_],s[N_+1];
long long lt(int l,int r){
    return r<l?0:(p[r]-p[l-1])*(n-l+1+1ll)-(s[l]-s[r+1]);
}
long long rt(int l,int r){
    return r<l?0:(p[r]-p[l-1])*(r+1ll)-(q[r]-q[l-1]);
}

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)scanf("%d",a+i),p[i]=p[i-1]+a[i],q[i]=q[i-1]+1ll*i*a[i];
    for(int i=n;i>=1;--i)s[i]=s[i+1]+1ll*(n-i+1)*a[i];
    scanf("%d",&q_);
    for(;q_--;){
        scanf("%d",&a_);
        if(a_==1)scanf("%*d");
        else{
            scanf("%d%d%d",&x,&y,&m);
            if(x+m-1>y){puts("0");continue;}
            int nrange=y-x+1-m+1;
            int pk=lo(nrange,m),p1=x+pk-1,p2=y-pk+1;
            //printf(" [%d %d] - range = %d, peak = %d, p1 = %d, p2 = %d\n",x,y,nrange,pk,p1,p2);
            printf("%lld\n",(p[p2]-p[p1-1])*1ll*pk+lt(x,p1-1)+rt(p2+1,y));
        }
    }
}

/*
 * queries
 *
 * when ask [l, r, m]
 * if r - l + 1 < m - zero
 * else
 * [1, 1, 1, 1, 1]
 * [1, 2, 2, 2, 2, 1]
 * [1, 2, 3, 3, 3, 2, 1]
 *
 *
 */

Compilation message

Main.c: In function 'main':
Main.c:16:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%d%d",&n,&k);
      |     ^~~~~~~~~~~~~~~~~~~
Main.c:17:26: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     for(int i=1;i<=n;++i)scanf("%d",a+i),p[i]=p[i-1]+a[i],q[i]=q[i-1]+1ll*i*a[i];
      |                          ^~~~~~~~~~~~~~~
Main.c:19:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%d",&q_);
      |     ^~~~~~~~~~~~~~~
Main.c:21:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%d",&a_);
      |         ^~~~~~~~~~~~~~~
Main.c:22:18: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         if(a_==1)scanf("%*d");
      |                  ^~~~~~~~~~~~
Main.c:24:13: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |             scanf("%d%d%d",&x,&y,&m);
      |             ^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 568 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 5 ms 704 KB Output is correct
9 Correct 4 ms 856 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1676 KB Output is correct
2 Correct 11 ms 2136 KB Output is correct
3 Correct 16 ms 2652 KB Output is correct
4 Correct 27 ms 4188 KB Output is correct
5 Correct 38 ms 5972 KB Output is correct
6 Correct 37 ms 5864 KB Output is correct
7 Correct 40 ms 6228 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 2908 KB Output isn't correct
2 Halted 0 ms 0 KB -